相关疑难解决方法(0)

我的C#程序中有一个整数列表.但是,我只在运行时知道列表中的项目数.

让我们说,为了简单起见,我的列表是{1,2,3}现在我需要生成所有可能的组合,如下所示.{1,2,3} {1,2} {1,3} {2,3} {1} {2} {3}

有人可以帮忙吗？

我有一个程序正在对Long.bitCount()进行大量调用,因此在一个CPU内核上需要33%的周期.有没有办法实现它比Sun JDK版本更快？

我试过了:

• 这个算法(我认为这正是JDK如何实现它)
• 在2 ⁸和2 ²²之间查找各种大小的表(一次查看几个位并添加结果)

但是,我没有比一个带有手动展开循环的2 ¹⁶ -entry查找表更好(大约27%的CPU.)
如何针对Java进行优化呢？

注意:这个问题是关于特定于Java的优化,但这个类似的(语言无关的)问题还有许多其他算法.

我试图了解HAMT的细节.我已经用Java实现了一个只是为了理解.我熟悉Tries,我认为我得到了HAMT的主要概念.

基本上,

两种类型的节点:

核心价值

Key Value Node:
  K key
  V value

指数

Index Node:
  int bitmap (32 bits)
  Node[] table (max length of 32)

1. 为对象生成32位哈希.
2. 一次遍历5位哈希.(0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31) 注意:最后一步(第7步)只有2位.
3. 在每个步骤中,找到位图中该5位整数的位置.例如integer==5 bitmap==00001
   1. 如果该位为1,则存在该部分哈希.
   2. 如果该位为0,则密钥不存在.
4. 如果密钥存在,通过计算位图中0和位置之间的1的数量,找到它在表中的索引.例如integer==6 bitmap==0101010101 index==3
   1. 如果表指向键/值节点,则比较键.
   2. 如果表指向索引节点,则转到2向前移动一步.

我不太了解的部分是碰撞检测和缓解.在链接的论文中,他提到了:

然后将现有密钥插入新的子哈希表中并添加新密钥.每次使用5个比特的散列时,碰撞的概率减少1/32.有时可能会消耗整个32位散列,并且必须计算新的散列以区分这两个密钥.

如果我要计算一个"新"哈希并将该对象存储在该新哈希中; 你怎么能够在结构中查找对象？在进行查找时,它不会生成"初始"哈希而不是"重新计算的哈希".

我肯定错过了什么.....

BTW:HAMT表现相当不错,它在我的测试中位于哈希映射和树图之间.

Data Structure                    Add time   Remove time     Sorted add time Sorted remove time   Lookup time     Size     
Java's Hash Map                   38.67 ms   18 ms           30 ms           15 …

我已经阅读了这个关于32位的SO问题,但64位数字呢？我应该屏蔽上下4个字节,对32位执行计数,然后将它们一起添加？

最近在我的谷歌采访中提到了这一点,我提供了一个涉及位移的答案,并且是O(n),但她说这不是最快的方式.我不明白,有没有办法计算位集而不必迭代提供的整个位？

__builtin_popcount对于MSVC-10,与GCC和Clang 相同的是什么？

我正在实现一个库,我广泛使用.Net BitArray类,需要等效的Java BitSet.Cardinality()方法,即返回设置的位数的方法.我正在考虑将其实现为BitArray类的扩展方法.平凡的实现是迭代和计数位集(如下所示),但我希望更快的实现,因为我将执行数千个集合操作并计算答案.有比下面的例子更快的方法吗？

count = 0;

for (int i = 0; i < mybitarray.Length; i++)
{

  if (mybitarray [i])
    count++;
}

我相信必须有一个更好的方法来做到这一点.我正在尝试对Flags枚举进行计数操作.在我尝试所有可能的值并计算成功的AND操作之前.

例如

[Flags]
public enum Skills
{
    None = 0,
    Skill1 = 1,
    Skill2 = 2,
    Skill3 = 4,
    Skill4 = 8,
    Skill5 = 16,
    Skill6 = 32,
    Skill7 = 64,
    Skill8 = 128
}

public static int Count(Skills skillsToCount)
{
   Skills skill;
   for (int i = 0; i < SkillSet.AllSkills.Count; i++)
   {
      skill = SkillSet.AllSkills[i];
      if ((skillsToCount & skill) == skill && skill != Skills.None)
         count++;
   }
   return count;
}

我确信必须有更好的方法来做到这一点,但必须患有精神障碍.谁能建议更好的解决方案？

以下是一个神奇的公式,它给出了一个数字中设置的位数(汉明重量).

/*Code to Calculate count of set bits in a number*/
int c;
int v = 7;
v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
printf(" Number of Bits is %d",c);
/*-----------------------------------*/

来自:http: //graphics.stanford.edu/~seander/bithacks.html

有谁能解释一下这背后的理由？

此问题来自2011 Codesprint(http://csfall11.interviewstreet.com/):

计算机科学的基础之一是知道数字如何以2的补码表示.想象一下,使用32位写下A和B之间的所有数字,包括2的补码表示.你会写下多少1？输入:第一行包含测试用例数T(<1000).每个下一个T行包含两个整数A和B.输出:输出T行,一行对应于每个测试用例.约束:-2 ^ 31 <= A <= B <= 2 ^ 31 - 1

样品输入:3 -2 0 -3 4 -1 4样品输出:63 99 37

说明:对于第一种情况,-2包含31 1后跟0,-1包含32 1和0包含0 1.因此,总是63.对于第二种情况,答案是31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

我意识到你可以使用-X中的1的数量等于(-X)= X-1的补码中的0的数量以加速搜索的事实.该解决方案声称有一个O(log X)递归关系用于生成答案但我不明白.解决方案代码可以在这里查看:https://gist.github.com/1285119

如果有人能解释这种关系是如何产生的,我将不胜感激!