2017-08-28 108 views
0

我有大约100,000个项目的大阵列和大约1000个项目的小阵列。我需要在大数组中搜索小数组中的每个字符串,并且我需要索引返回的字符串。 (所以我需要搜索100k阵列1000次)perl - 搜索大/排序/数组作为字符串的索引

大数组已被排序,所以我猜想某种二进制斩波类型搜索会比使用foreach循环更有效率(使用'last'来中断当找到循环),这是我开始。 (这第一次尝试导致大约30米的比较!)

是否有一个内置的搜索方法,可以产生更高效的结果,或者我将不得不手动编码二进制搜索?我也想避免使用外部模块。

为了这个问题的目的,假设我需要在大的排序数组中找到单个字符串的索引。 (我只提了1000个项目给予尺度的概念)

+0

为什么你想避免外部模块?不是我知道一个完全符合法案的人,但你可以尝试[tcgrep -1F](http://search.cpan.org/perldoc?tcgrep),看看它是否足够快,并修改它以返回索引;我没有找过其他CPAN模块。 – reinierpost

+1

还有[List :: BinarySearch](http://search.cpan.org/perldoc?List%3A%3ABinarySearch)。在实现你自己的任何东西之前,我会尝试使用模块。 – reinierpost

+0

该数组是否已存在于Perl数组中,还是存储在磁盘上?在后一种情况下,它会适合你的主存吗?如果不是这样,即使这样排除了二分搜索,也可能不会立即将其全部存入主内存。 – reinierpost

回答

4

这听起来像经典的哈希使用的情况下,

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

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

那么,如果我只是想在大数组中找到字符串“bob”的索引,那该如何工作呢? – jxm

+0

@jxm'$ index_for {“bob”}'('bob'周围的引号是可选的) –

2

使用二进制搜索可能是最佳的位置。二进制搜索只需要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)没有任何比较可能的,你必须先创建哈希表。这可能会也可能不会更快。请注意,散列只能使用字符串作为键。如果你的物品是具有他们自己的平等概念的复杂物体,那么你必须首先派生一个合适的钥匙。