perl - 搜索大/排序/數組作爲字符串的索引

我有大約100,000個項目的大陣列和大約1000個項目的小陣列。我需要在大數組中搜索小數組中的每個字符串，並且我需要索引返回的字符串。（所以我需要搜索100k陣列1000次）perl - 搜索大/排序/數組作爲字符串的索引

大數組已被排序，所以我猜想某種二進制斬波類型搜索會比使用foreach循環更有效率（使用'last'來中斷當找到循環），這是我開始。（這第一次嘗試導致大約30米的比較！）

是否有一個內置的搜索方法，可以產生更高效的結果，或者我將不得不手動編碼二進制搜索？我也想避免使用外部模塊。

爲了這個問題的目的，假設我需要在大的排序數組中找到單個字符串的索引。（我只提了1000個項目給予尺度的概念）

2017-08-28 jxm

爲什麼你想避免外部模塊？不是我知道一個完全符合法案的人，但你可以嘗試[tcgrep -1F]（http://search.cpan.org/perldoc?tcgrep），看看它是否足夠快，並修改它以返回索引;我沒有找過其他CPAN模塊。 – reinierpost

還有[List :: BinarySearch]（http://search.cpan.org/perldoc?List%3A%3ABinarySearch）。在實現你自己的任何東西之前，我會嘗試使用模塊。 – reinierpost

該數組是否已存在於Perl數組中，還是存儲在磁盤上？在後一種情況下，它會適合你的主存嗎？如果不是這樣，即使這樣排除了二分搜索，也可能不會立即將其全部存入主內存。 – reinierpost

這聽起來像經典的哈希使用的情況下，

my %index_for = map { $large_array[$_] => $_ } 0 .. $#large_array; 

print "index in large array:", $index_for{ $small_array[1000] };

來源

2017-08-28 10:08:13

那麼，如果我只是想在大數組中找到字符串「bob」的索引，那該如何工作呢？ – jxm

@jxm'$ index_for {「bob」}'（'bob'周圍的引號是可選的） –

使用二進制搜索可能是最佳的位置。二進制搜索只需要O（log n）比較（這裏〜每次查找〜17次比較）。

或者，你可以創建一個映射項將其索引的哈希表：

my %positions; 
$positions{ $large_array[$_] } = $_ for 0 .. $#large_array; 

for my $item (@small_array) { 
    say "$item has position $positions{$item}"; 
}

雖然現在每個查找是O（1）沒有任何比較可能的，你必須先創建哈希表。這可能會也可能不會更快。請注意，散列只能使用字符串作爲鍵。如果你的物品是具有他們自己的平等概念的複雜物體，那麼你必須首先派生一個合適的鑰匙。

來源

2017-08-28 10:08:30 amon

perl - 搜索大/排序/數組作爲字符串的索引

回答

相關問題