| 導購 | 订阅 | 在线投稿
分享
 
 
 

使用插值在序列中查找遺漏的值

來源:互聯網  2008-05-31 22:07:57  評論

在有些應用程序中,序列化值的範圍能夠連續是重要的。當在這個序列新增值的時候,它可能會在序列中優先挑選一個「空的(hole)」或者遺漏的值來填充,而不是取序列最大值之後的下一個值,或者使用一個序號産生器。

例如電話號碼、社會安全號碼和IP地址都有非常嚴格的範圍限制,所以說最好使用未用的號碼來填充。

當數據庫中有很多值的時候經常會出現這個問題。遺漏的值明顯是不被索引的,所以定位遺漏的數字的最明顯的方法是順序查詢所有的值,然後在碰到期望的值的時候將其返回:

REM - table in question is "massive" with a sequence "id"

set serveroutput on;

set timing on;

declare

l_idinteger := null;

begin

for row in (select id from massive order by id) loop

if l_id is null then

l_id := row.id;

else

l_id := l_id + 1;

end if;

exit when l_id != row.id;

end loop;

dbms_output.put_line('lowest missing value = 'l_id);

end;

/

另外一個方法是使用「分而治之」的策略。假如我們已經知道在一個給定的範圍內應該有多少個值,並且表上建有索引的話,我們可以相當快地取得實際的記錄的條數。假如有一個遺漏的值,實際的記錄條數將會比期望的記錄的條數少。

我們可以應用相同的方法檢測在較小的一半是否有遺漏的值。假如有的話,就繼續將其對分。假如沒有遺漏的值,我們檢測另外一半。最後,我們將要檢測的記錄集合的大小能夠正好只找出遺漏的數據:

下面是這種技術的PL/SQL示例:

set serveroutput on

declare

l_min integer;

l_max integer;

actual_countinteger;

eXPected_countinteger;

halfinteger;

begin

select max(id),min(id),count(*)

into l_max,l_min,actual_count

from massive;

expected_count := l_max - l_min + 1;

if expected_count = actual_count then

dbms_output.put_line('there are no missing values');

end if;

while l_max - l_min = 1 loop

-- try lower half of range

half := trunc(expected_count/2);

expected_count := expected_count - half;

select count(*)

into actual_count

from massive

where id between l_min and l_max - half;

exit when actual_count = 0;

if actual_count = expected_count then

-- missing value must be in upper half

l_min := l_min + half;

else

l_max := l_max - half;

end if;

end loop;

end;

/

對于具有一百萬條記錄,並且有一個正規索引的表,假如其中漏值只有一個話,有非正式的結果表明第二個腳本的執行速度是第一個的五倍。

  在有些應用程序中,序列化值的範圍能夠連續是重要的。當在這個序列新增值的時候,它可能會在序列中優先挑選一個「空的(hole)」或者遺漏的值來填充,而不是取序列最大值之後的下一個值,或者使用一個序號産生器。 例如電話號碼、社會安全號碼和IP地址都有非常嚴格的範圍限制,所以說最好使用未用的號碼來填充。      當數據庫中有很多值的時候經常會出現這個問題。遺漏的值明顯是不被索引的,所以定位遺漏的數字的最明顯的方法是順序查詢所有的值,然後在碰到期望的值的時候將其返回:      REM - table in question is "massive" with a sequence "id"   set serveroutput on;   set timing on;   declare     l_id    integer := null;   begin     for row in (select id from massive order by id) loop       if l_id is null then         l_id := row.id;       else         l_id := l_id + 1;       end if;       exit when l_id != row.id;     end loop;     dbms_output.put_line('lowest missing value = 'l_id);   end;   /      另外一個方法是使用「分而治之」的策略。假如我們已經知道在一個給定的範圍內應該有多少個值,並且表上建有索引的話,我們可以相當快地取得實際的記錄的條數。假如有一個遺漏的值,實際的記錄條數將會比期望的記錄的條數少。      我們可以應用相同的方法檢測在較小的一半是否有遺漏的值。假如有的話,就繼續將其對分。假如沒有遺漏的值,我們檢測另外一半。最後,我們將要檢測的記錄集合的大小能夠正好只找出遺漏的數據:      下面是這種技術的PL/SQL示例:      set serveroutput on   declare     l_min        integer;     l_max        integer;     actual_count    integer;     eXPected_count   integer;     half        integer;   begin     select max(id),min(id),count(*)      into l_max,l_min,actual_count      from massive;     expected_count := l_max - l_min + 1;     if expected_count = actual_count then       dbms_output.put_line('there are no missing values');     end if;     while l_max - l_min = 1 loop       -- try lower half of range       half := trunc(expected_count/2);       expected_count := expected_count - half;       select count(*)        into actual_count        from massive        where id between l_min and l_max - half;       exit when actual_count = 0;       if actual_count = expected_count then         -- missing value must be in upper half         l_min := l_min + half;       else         l_max := l_max - half;       end if;     end loop;   end;   /      對于具有一百萬條記錄,並且有一個正規索引的表,假如其中漏值只有一個話,有非正式的結果表明第二個腳本的執行速度是第一個的五倍。
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 熱帖排行
 
王朝網路微信公眾號
微信掃碼關註本站公眾號 wangchaonetcn
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有