算法的力量：位运算在排序与搜索中的应用

gxqcn

原帖由 无心人 于 2009-4-16 08:10 发表
TO GxQ 4#
确实是4G bit而不是Byte啊
但位操作的偏移是有符号数

即实际的范围是操作数的正负2^31范围内

可sizeof 的单位是 byte，
也就是说地址的单位是byte啊，
怎么会与bit挂上钩了？

kon3155

原帖由 shshsh_0510 于 2009-4-15 19:21 发表

他这个使用内存较大，自己构造数据类型的好。
对于他这个应用，实际上在不在内存没关系，反正是遍历一边，结果存在硬盘一样。
这个是在说这个道理：当样本的数目多到和整个空间相近似，排序就意义不大了

样本的数目和整个空间还是相差10%的，排序的意义真的不大了？自己构造数据类型的话怎么才能减少内存的使用呢？

无心人

TO 11#
你查查BT等几个指令就明白了

和sizeof无关
因为其操作数是32位的
所以范围是2^32

gxqcn

这与 BT 等汇编指令不相干吧？
再说 BT 等指令，你即便输入一个很大数，实际上起作用仅是除以寄存器bit数后的余数。

因为32位系统下的指针是32位的，它最多可寻址2^32个byte位置，
所以我还是坚持是byte而非bit的说法。

litaoye

昨天数错了,不好意思，少说了1个,应该正好是9亿个,如果不考虑首位为0的情况,O(1)空间就可以了,也无需定义啥数组,
其实我想说的是,有些文章里为了说明自己算法的优势,往往搞一些极端情况,而实际上这种情况出现的概率是非常小的。

关于寻址单位的问题，我不懂，也不敢乱说，但我个人认为似乎应当是byte。

原帖由 gxqcn 于 2009-4-16 07:36 发表
如果规定首位非0，则有9个数字可选，后面每位均有10个数字可选，
则总共正好有9亿种组合，而不是楼上说的还差1个。

不过，如果是该规定，显然无须特殊排序，可对任意值直接定位。

也就是说，这里的9位整数应该 ...

无心人

不是一码事啊
哎
乱了，咱别打搅别人了

medie2005

算法好象没什么用哦.
最重要的是做事方法.

仙剑魔

你们都被骗了...
这个无非是计数排序的特殊情况(数据只出现0次或1次)
9亿(9E8)条不重复的9位整数(1E9=10E8)
也就是说10亿个数字里出现了9亿个
那个方法只是把计数排序猥琐的改成标记法,用来标记数字是否出现过而已...

shshsh_0510

对于他的这两个问题,他的做法是很恰当的,不会这么容易被骗吧

原帖由 kon3155 于 2009-4-16 09:29 发表


样本的数目和整个空间还是相差10%的，排序的意义真的不大了？自己构造数据类型的话怎么才能减少内存的使用呢？

上边我说自己构造数据类型，但可能比较多余，数据量还没这么大（几百兆）。
一般位操作，用C语言的话就是 无符号整数呗。我说构造自己的数据类型，就是说要加一点结构化信息，比如做成B树，以便于寻址
至于怎么减少内存：用这个方法不能减少内存。
这个问题就是在10亿空间中的9亿排序。
普通的排序算法是在无穷空间中的X个进行排序。
从上边描述可以看出区别：只要求输出是一个有序集，在有限空间中除了排序方法，还可以用生成方法。
只不过，如果整体空间很大，而要排序的子集很小时，用通常的排序方法效率要高的多（即放弃使用整体空间的结构信息）
至于bit数组可以有多大的问题：首先,平常说的XXG,XXM的内存大小单位是byte.
             对于处理器， 寻址寄存器是32位，数据寄存器是32位，所以处理 32位*32位的空间是没啥问题的，如果自己再加些处理，多大都没问题吧
            但一般操作系统会更限制，比如我用的winxp，进程最大空间4G，用户态程序最多3G,那最大就是3G了，单位应该也是byte吧

kon3155

原帖由 shshsh_0510 于 2009-4-17 08:44 发表
对于他的这两个问题,他的做法是很恰当的,不会这么容易被骗吧
...

“他的做法是很恰当的”？被骗从何说起啊？