|
|
楼主
楼主 |
发表于 2012-4-22 15:03:44
|
只看该作者
区间树结构搜寻算法
区间树结构搜寻算法：
设原始区间为【A,B】
A：数值型变量数据的第一条观测位置
B：数值型变量数据的最后一条观测的位置
第一步：搜寻出原始区间【A,B】中的最大（或最小）值点，并记录该点值的大小，所在的观测位置，值的类型为峰（或谷）。
第二步：对满足搜寻条件的新区间中的数据进行下一类型值的搜寻（峰和谷间隔相邻），并进一步对搜寻出的点判断是否符合条件，如果不符合则该点不能产生两个新的区间，并停止对该原符合条件的区间进行搜寻，否则记录改点值的大小，观测位置及值的类型，并将产生两个新的区间。
………
……判断上一步产生的新区间是否满足搜寻条件，满足则继续向下搜寻……,直到把所有符合条件观测点搜寻完，最终将所有符合条件的点记录在一个新的数据集中。
区间满足搜寻的条件：
1. 若区间端点包含有起点A或终点B时，此时只需搜寻一个点，则区间大小需大于最小值105。
2. 若不包含，则此时需要搜寻同时搜寻一个峰值和一个谷值，区间大小需大于252。
对不含区间端点A和B搜寻区间【P1，P2】的说明：
设P1(峰)，P2（谷），则该区间将搜寻一个谷值和一个峰值，靠近端点P1的搜寻点类型为谷，靠近端点P2的搜寻点的类型为峰，且搜寻出的峰值和谷值两个点，要么同时有效，要么同时无效。无效则停止对区间【P1，P2】继续向下搜寻。
判断搜寻出的点是否有效的条件；（第一个搜寻出的点无需判断）
1. 相邻峰值与谷值间值的关系为： （峰值-谷值）/峰值>0.3;
2. 产生的所有新区间都必须大于区间的最小值105（除含有A,B端点的区间）
test数据
[code:2kd0a3ju]data test;
input zxj;
obs=_n_;
cards;
1591.429
1590.853
1551.21
1607.21
1614.492
1628.799
1638.487
1642.014
1635.38
1661.627
1647.823
1680.246
1732.673
1755.014
1740.36
1795.745
1855.677
1888.618
1895.061
1895.767
1975.702
2006.376
1925.962
1842.142
1876.53
1919.004
1959.2
1871.506
1868.625
1767.015
1702.139
1718.854
1707.549
1815.308
1817.009
1796.271
1728.563
1774.712
1760.544
1756.865
1748.894
1763.156
1817.908
1833.309
1880.557
1868.282
1925.359
1935.61
1881.664
1967.24
2010.042
2006.121
2027.037
2063.858
2075.052
2038.48
2049.456
1994.802
2023.329
2090.875
2154.827
2161.109
2158.898
2170.657
2142.248
2191.446
2175.44
2092.666
2097.319
2075.326
2006.775
2010.764
2073.909
2093.634
2154.849
2180.987
2217.253
2194.913
2188.221
2121.58
2154.541
2170.524
2158.996
2162.472
2173.92
2191.508
2169.444
2119.604
2116.761
2123.147
2118.324
2137.027
2183.314
2199.521
2219.056
2213.501
2194.586
2180.983
2195.057
2237.25
2203.172
2160.019
2177.934
2177.453
2202.525
2233.549
2265.053
2250.103
2243.303
2279.777
2259.257
2254.032
2284.016
2267.792
2284.893
2312.05
2326.244
2348.108
2344.845
2349.294
2387.225
2391.397
2413.44
2457.831
2510.966
2477.626
2494.586
2561.123
2511.865
2552.643
2555.59
2558.565
2623.435
2664.671
2493.721
2522.032
2606.396
2671.346
2700.117
2721.617
2662.313
2569.6
2579.334
2579.147
2440.571
2443.015
2357.763
2219.685
2252.128
2140.198
2222.258
2259.115
2275.111
2201.557
2275.587
2281.602
2232.038
2077.574
2068.125
2078.375
2178.609
2191.244
2206.744
2245.622
2277.258
2254.725
2278.269
2317.343
2318.093
2283.807
2338.423
2271.822
2297.218
2247.674
2204.196
2180.769
2163.148
2114.444
2098.784
2110.421
2213.5
2198.77
2225.64
2246.667
2241.269
2244.67
2289.918
2318.888
2305.295
2295.344
2324.319
2314.624
2253.088
2265.539
2217.836
2237.514
2292.185
2326.273
2342.132
2374.822
2398.132
2405.608
2417.205
2426.756
2430.766
2455.613
2519.877
2517.901
2508.691
2534.23
2528.81
2554.223
2452.353
2507.633
2410.13
2359.297
2456.584
2493.685
2512.498
2520.807
2528.42
2555.261
2516.249
2451.774
2469.327
2463.679
2490.185
2474.125
2459.201
2394.458
2346.701
2362.837
2291.713
2320.368
2381.39
2380.369
2408.98
2413.566
2430.027
2441.034
2426.07
2443.498
2441.108
2407.755
2419.262
2440.857
2496.178
2453.958
2498.126
2512.508
2554.061
2549.841
2485.197
2486.646
2443.763
2404.856
2325.771
2307.867
2332.425
2328.314
2279.203
2263.588
2304.093
2310.058
2272.085
2277.823
2293.953
2321.366
2321.032
2326.739
2336.089
2328.739
2367.092
2389.154
2378.33
2400.105
2395.693
2423.662
2358.945
2372.337
2387.1
2383.365
2351.445
2346.352
2311.835
2283.732
2299.842
2350.3
2342.566
2362.077
2376.244
2355.584
2363.482
2329.024
2360.009
2405.117
2400.026
2392.62
2425.489
2436.475
2434.841
2426.189
2419.384
2438.958
2447.054
2455.727
2462.972
2448.594
2430.703
2306.627
2311.448
2358.082
2331.644
2330.842
2328.785
2271.64
2250.284
2216.002
2207.499
2186.421
2219.059
2128.379
2067.287
2059.506
2014.13
2010.755
2060.485
2047.185
1922.147
1956.146
1954.822
1926.366
1957.129
2035.901
1995.73
2009.623
2051.074
2042.083
1981.795
1958.185
1978.166
1956.082
1957.691
1940.472
1958.371
2002.023
1993.275
1999.049
1986.098
1955.213
2004.662
2011.419
1985.952
1978.012
1955.393
1938.26
1847.012
1823.207
1801.076
1815.584
1801.755
1831.928
1849.461
1839.656
1883.849
1902.283
1874.909
1895.568
1860.469
1852.913
1898.04
1943.797
1958.286
1983.013
1986.767
2009.181
1995.731
2039.256
2046.824
2038.23
2066.831
2029.078
2042.904
2034.277
2074.633
2085.238
2014.92
2026.354
1997.517
2030.563
2091.449
2108.351
2101.147
2108.977
2077.407
2077.465
2088.883
2035.512
2046.7
2055.46
2094.503
2082.829
2055.904
2081.452
2096.798
2130.529
2140.019
2148.955
2110.505
2119.829
2154.256
2161.101
2124.012
2093.75
2078.89
2067.465
2068.673
2107.028
2087.517
2079.825
2116.591
2177.973
2227.135
2248.704
2271.219
2276.65
2358.417
2372.491
2416.405
2405.148
2381.926
2397.468
2453.215
2464.436
2426.451
2408.423
2414.33
2488.741
2503.5
2468.179
2520.894
2554.439
2569.74
2539.993
2516.721
2516.305
2344.759
2369.752
2302.143
2258.791
2272.26
2313.332
2310.227
2247.326
2292.877
2336.701
2316.307
2333.315
2281.126
2281.436
2291.995
2300.463
2295.488
2307.375
2318.84
2317.948
2338.848
2414.426
2428.394
2400.995
2382.503
2397.076
2368.831
2411.311
2394.858
2361.592
2329.388
2280.133
2239.943
2275.52
2280.64
2322.556
2378.93
2387.569
2373.006
2367.425
2336.338
2339.254
2342.658
2350.475
2320.798
2245.986
2236.298
2320.088
2254.349
2313.992
2318.55
2280.646
2343.276
2409.685
2418.827
2479.05
2450.745
2442.023
2457.891
2472.31
2520.295
2530.532
2555.63
2570.346
2532.856
2561.485
2467.659
2475.321
2491.506
2486.801
2536.891
2534.234
2502.694
2467.326
2505.738
2541.349
2543.53
2567.01
2528.296
2495.295
2486.881
2443.752
2471.949
2429.709
2453.14
2444.318
2446.132
2479.277
2464.17
2484.99
2476.845
2428.322
2421.015
2396.409
2420.103
2429.992
2452.628
2467.049
2451.843
2469.538
2500.43
2481.204
2481.128
2475.825
2429.676
2441.408
2461.63
2467.785
2416.588
2395.64
2377.041
2317.788
2355.388
2374.203
2331.477
2314.888
2326.479
2346.958
2350.803
2350.267
2307.892
2327.884
2312.033
2318.719
2330.843
2309.17
2300.732
2228.188
2222.996
2198.517
2181.626
2159.834
2145.812
2189.553
2198.113
2169.753
2196.234
2211.671
2219.749
2175.716
2184.466
2177.938
2206.114
2184.306
2150.658
2136.016
2117.782
2132.136
2131.381
2165.409
2224.903
2246.436
2249.923
2221.065
2252.687
2243.45
2288.389
2296.524
2295.532
2281.904
2283.8
2295.79
2253.682
2280.233
2284.382
2285.89
2283.889
2260.877
2249.662
2225.494
2225.085
2143.747
2153.999
2169.465
2152.467
2125.059
2129.293
2105.764
2096.897
2109.211
2063.113
1968.051
1965.658
1983.076
2005.842
2025.218
2050.006
2026.467
2021.183
1986.765
1964.306
1938.931
1972.085
1968.864
2029.884
2027.109
1997.916
1987.625
1983.495
1965.554
1943.468
1906.692
1896.229
1930.214
1908.261
1903.625
1875.558
1892.319
1891.826
1887.429
1852.712
1859.061
1925.358
1864.948
1862.331
1837.546
1851.49
1834.217
1814.772
1799.036
1779.468
1782.948
1846.533
1865.702
1855.598
1856.49
1804.864
1800.512
1748.753
1732.34
1774.598
1809.028
1832.191
1835.598
1874.42
1872.079
1872.515
1902.659
1912.393
1928.797
1908.947
1893.14
1908.075
1874.44
1865.472
1900.056
1910.128
1859.613
1846.852
1811.144
1815.261
1808.497
1792.222
1785.997
1773.125
1769.735
1796.329
1729.294
1762.32
1742.306
1713.26
1707.101
1714.379
1712.584
1700.542
1683.789
1645.934
1621.258
1577.046
1609.816
1601.909
1594.909
1567.765
1567.265
1584.557
1570.096
1545.7
1545.565
1546.659
1567.04
1531.298
1508.065
1515.069
1563.398
1626.905
1618.593
1616.407
1581.741
1549.7
1633.967
1612.701
1636.164
1652.322
1626.779
1632.542
1613.508
1642.381
1654.607
1654.113
1621.885
1662.551
1664.987
1676.625
1680.044
1673.391
1701.045
1689.209
1692.368
1693.211
1705.573
1726.707
1734.787
1763.832
1772.083
1773.203
1748.198
1750.347
1779.162
;[/code:2kd0a3ju]
这是本人下来写的(参照)，用sas的data步实现，代码繁多，且调试还有一点问题，我用的遍历方法是：找到第一个点后，先一直向左遍历，在一直向右遍历到，最后又向回遍历到第一个点。感觉写的复杂了 ....希望有更好点的简单方法来实现，且调试没问题。期待高手们的出现...
[code:2kd0a3ju]proc sql noprint;
select obs,max(zxj)
into:firstpos,:firstvalue
from lab3.sh000034
having zxj=max(zxj);
quit;
%put &firstpos./&firstvalue.;
%macro remove(A,B);
if k ne 0 then do; &A=&B; &B=pos[k];k=k-1;end;
else do;stop;end;
%mend;
%macro skip(size,mark,pos=left);
if abs(right-left)<&size. then do;
if &pos.=%str(left) then do;%remove(left,right);end;
else do;%remove(right,left);end;
goto mark;
end;
else goto &mark.;
%mend;
%macro select(uporlow,p=p,v=v);
&p.=ifn(&v. %if &uporlow.=%str(up) %then <=;%else >=;zxj,&p.,&p.+1);
&v.=ifn(&v. %if &uporlow.=%str(up) %then <=;%else >=;zxj,&v.,zxj);
%mend;
%macro add(p,v);
k+1;value[k]=&v.;pos[k]=&p.;
flag[k]=ifc(flag[k-1]='up','low','up');
%mend;
%macro judge(condition);
%if &condition.=1 %then %do;
abs(value[k]-v)/max(value[k],v)<0.3 or abs(pos[k]-p)<105
%end;
%else %do;
abs(value[k-1]-v1)/max(value[k-1],v1)<0.3 or abs(pos[k-1]-p1)<105 or
abs(value[k]-v2)/max(value[k],v2)<0.3 or abs(pos[k]-p2)<105 or
abs(v1-v2)/max(v1,v2)<0.3 or abs(p1-p2)<105
%end;
%mend;
%macro look(kinds,period);
%if &kinds.=1 %then %do;
if i=left then do;v=zxj;p=i;end;
if flag[k]='up' then do;%select(low);end;
else do;%select(up);end;
if i=right then do;
if %judge(&kinds.) then do;%remove(left,right);goto mark;end;
else do;
%add(p,v);
%if &period.=%str(left) %then right;%else left;=p;
obs=pos[k];zxj=value[k];uporlow=flag[k];output;
goto mark;
end;
end;
else continue;
%end;
%else %do;
if i<ceil(abs((right-left)/2)) then do;
if i=left then do;v1=zxj;p1=i;end;
if flag[k-1]='up' then do;%select(low,p=p1,v=v1);end;
else do;%select(up,p=p1,v=v1);end;
end;
else do;
if i=ceil(abs((right-left)/2)) then do;v2=zxj;p2=i;end;
if flag[k]='up' then do;%select(low,p=p2,v=v2);end;
else do;%select(up,p=p2,v=v2);end;
end;
if i=right then do;
if %judge(&kinds.) then do;
%if &period.=%str(leftmid) %then %do; %remove(left,right);%end;
%else %do; %remove(right,left);%end;
end;
else do;
%if &period.=%str(leftmid) %then %do;%add(p2,v2);%add(p1,v1);right=value[k];%end;
%else %do;%add(p1,v1);%add(p2,v2);left=value[k];%end;
obs=pos[k-1];zxj=value[k-1];uporlow=flag[k-1];output;
obs=pos[k];zxj=value[k];uporlow=flag[k];output;
goto mark;
end;
end;
else continue;
%end;
%mend;
options nomprint nomlogic nosymbolgen;
data want(keep=obs zxj uporlow);
array value{20};
array pos{20};
array flag{20} $;
retain k 1 left right;
pos[k]=n;k+1; left=1; right=n;
value[k]=&firstvalue.;pos[k]=&firstpos.;flag[k]='up';
obs=pos[k];zxj=value[k];uporlow=flag[k];output;
do until(k=0);
mark: do i=left to right;
set lab3.sh000034 nobs=n point=i;
put i= n= left= right=;
select;
when(left eq 1 and right le &firstpos.) do;%skip(105,left);end;
when(left gt 1 and right le &firstpos.) do;%skip(504,leftmid);end;
when(left ge &firstpos. and right eq n) do;%skip(105,right);end;
when(left ge &firstpos. and right lt n) do;%skip(504,rightmid,pos=right);end;
otherwise;
end;
left: %look(1,left);
leftmid: %look(2,leftmid);
right: %look(1,right);
rightmid: %look(2,rightmid);
end;
end;
run;
[/code:2kd0a3ju] |
|
