需要超高速二进制搜索，具有超高速icomparer [英] need superfast binarysearch, with superfast icomparer
问题描述
我的动机如下：
我必须二百万次二元搜索[]这几百元一百万美元的大项目。这需要时间，虽然我使用
Array.Binarysearch< long>。所以我尽量保持比较方法尽可能精简
，因为它被召唤了几千万次。
如果整数最快的话我想是这样的方式：
public int比较（int a，int b）
{
返回ab; < br $>
}
prob是returnval需要是一个整数，因为
binarysearch-method适用于int我所知。如果我会写b
$
public int比较（长a，长b）
{
返回ab;
}
错误，或者我写...
public int比较（长a，长b）
{
return（int）（ab）;
}
i松散的信息，可能会导致错误的结果。
对于长类型或任何知道某人的人来说，任何超快的方式都有任何想法
以长型为输入的binarysearch-method？
为什么需要比较方法？你的实现（返回ab）与
的作用相同，默认比较长。
如果有什么我想要的，那么逻辑比较可能比扣除数字更快
：
int比较（长a，长b）
{
if（a> b）返回1;
else if（a< b）返回-1;
否则返回0;
}
" solandre"写道：
我的动机如下：
我必须二百万次使用二次搜索[]这是几百万个大项目。这需要时间，虽然我使用的是Array.Binarysearch< long>。所以我尽量保持比较方法尽可能瘦，因为它被召唤了几千万次。
如果是整数，最快的方法就是这样我想： br />
public int比较（int a，int b）
{
返回ab;
}
概率是returnval需要是一个整数，因为就我所知，
binarysearch-method适用于int。如果我愿意写......
public int比较（长a，长b）
{
返回ab;
}
是一个错误，或者我写...
public int比较（长a，长b）
{
return（int）（ab）; <我错了信息，可能会导致错误的结果。
对于长类型或任何知道二元搜索的人来说，这是一种超快速方式的想法 - 需要长型输入的方法吗？
感谢
我希望最好的表现是通过在
不安全代码中实现搜索（可能带有汇编程序）。
IComparable接口等实现搜索和
排序_complex_结构非常容易编码（可能以牺牲
性能为代价）。但你似乎没有使用复杂的结构，所以只需使用
简单的代码并称之为好。
solandre写道：我的动机如下：
我必须二百万次二次研究[]是几百万件物品。这需要时间，虽然我使用的是Array.Binarysearch< long>。所以我尽量保持比较方法尽可能精益，因为它被召唤了几千万次。
1.您正在寻找的物品是否是一个大的分类
集合？如果他们是你，你可以通过线性移动同时收集
集合进行查找。
2.如果您的输入是作为未分类的集合进入它可能更快
对它进行排序并转到1.
3.也许您可以使用字典代替项目？如果你只需要b $ b需要决定会员资格。长片的哈希集可以非常快。如果推动
推动你可以实现你自己的hastset和
获得*极快*性能。
public int Compare（长a，长b）
{
返回（int）（ab）;
}
我信息松散，可能导致错误的结果。
是的，这肯定会非常糟糕。
对于长型或任何知道二元搜索的人来说，任何想法都是超快的方式 - 使用long类型作为输入的方法？
1.尝试使用基准测试：
public int Compare（long a ，长b）{
if（a == b）
返回0;
else if（a< b）
返回-1;
其他
返回1;
}
是否足够快？
2.你可以编写自己的二进制搜索。
3.如果代码是*仍然*不足够快，你可以进入境界
的不安全代码和/或编写你自己的哈希集。
-
Helge Jensen
mailto：他********** @ slog.dk
sip：他********** @ slog.dk
- =>塞巴斯蒂安的封面音乐： http://ungdomshus.nu < = -
my motivation is as follows:
i have to binarysearch several million times an long[] that is several
million items big. this costs time, although i use
Array.Binarysearch<long>. so i try to keep the Compare-method as lean
as possible, as it is summoned several 10 million times.
in case of an integer the fastest way would be this i think:
public int Compare(int a, int b)
{
return a-b;
}
the prob is the returnval needs to be an integer, because the
binarysearch-method works with an int as far as i know. if i would
write...
public int Compare(long a, long b)
{
return a-b;
}
its an error, or i write...
public int Compare(long a, long b)
{
return (int)(a-b);
}
i loose information, likely leading to incorrect results.
any idea for a superfast way for long-types or anybody who knows a
binarysearch-method that takes a long-type as input?
thanks
Why do you need a compare method? Your implementation (return a-b) works the
same as the default comparison for long.
If there''s somehting I''m missing though, logical comparison might be faster
than subtracting the numbers:
int Compare(long a, long b)
{
if (a > b) return 1;
else if (a < b) return -1;
else return 0;
}
"solandre" wrote:
my motivation is as follows:
i have to binarysearch several million times an long[] that is several
million items big. this costs time, although i use
Array.Binarysearch<long>. so i try to keep the Compare-method as lean
as possible, as it is summoned several 10 million times.
in case of an integer the fastest way would be this i think:
public int Compare(int a, int b)
{
return a-b;
}
the prob is the returnval needs to be an integer, because the
binarysearch-method works with an int as far as i know. if i would
write...
public int Compare(long a, long b)
{
return a-b;
}
its an error, or i write...
public int Compare(long a, long b)
{
return (int)(a-b);
}
i loose information, likely leading to incorrect results.
any idea for a superfast way for long-types or anybody who knows a
binarysearch-method that takes a long-type as input?
thanks
I expect the best performance would be achieved by implementing the search in
unsafe code (perhaps with assembler).
The IComparable interface and the like make implementing searching and
sorting _complex_ structures very easy to code (perhaps at the expense of
performance). But you don''t seem to be using a complex structure, so just use
straightforward code and call it good.
solandre wrote:my motivation is as follows:
i have to binarysearch several million times an long[] that is several
million items big. this costs time, although i use
Array.Binarysearch<long>. so i try to keep the Compare-method as lean
as possible, as it is summoned several 10 million times.
1. Are the items you are looking for coming in as one big sorted
collection? if they are you can do your lookup by linear travesing both
collections at the same time.
2. If your input is coming in as an unsorted collection it may be faster
to sort it and goto 1.
3. Perhaps you could use a dictionary for the items instead? if you only
need to decide membership. Hashsets with longs can be extremely fast. If
push comes to shove you can implement your own hastset for the longs and
get *extremely* fast performance.
public int Compare(long a, long b)
{
return (int)(a-b);
}
i loose information, likely leading to incorrect results.
Yes, that would certainly be very bad.
any idea for a superfast way for long-types or anybody who knows a
binarysearch-method that takes a long-type as input?
1. try benchmarking using:
public int Compare(long a, long b) {
if ( a == b )
return 0;
else if ( a < b )
return -1;
else
return 1;
}
is it fast enough?
2. you can write your own binary-search.
3. if the code is *still* not fast enough, you could step into the realm
of unsafe code and/or write your own hash-set.
--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-
这篇关于需要超高速二进制搜索，具有超高速icomparer的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
