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

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

來源:互聯網  2008-05-19 08:57:41  評論

在有些應用程序中,序列化值的範圍能夠連續是重要的。當在這個序列新增值的時候,它可能會在序列中優先挑選一個「空的(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;

/

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

  在有些應用程序中,序列化值的範圍能夠連續是重要的。當在這個序列新增值的時候,它可能會在序列中優先挑選一個「空的(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;   /   對于具有一百萬條記錄,並且有一個正規索引的表,如果其中漏值只有一個話,有非正式的結果表明第二個腳本的執行速度是第一個的五倍。   
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 熱帖排行
 
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有