非阻塞算法生成唯一的负数

我最近重构了一段用于生成唯一负数的代码.
编辑:多个线程获取这些ID并将其作为键添加到DB; 数字必须是负数才能轻易识别 - 在测试会话结束时,它们将从数据库中删除.

我的Java算法如下所示:

private final Set seen = Collections.synchronizedSet(new HashSet());
public Integer generateUniqueNegativeIds() {
    int result = 0;
    do {
        result = random.nextInt();
        if (result > 0) {
            result *= -1;
        }
    } while (!seen.add(result));
    return result;
}

上面的代码结构,以及对set和"retry"循环的推测性添加,使我认为有一个等效的非阻塞算法用任何原子变量替换同步集.

我做了一些尝试使用原子变量重写,但都失败了多线程攻击测试.

是否有优雅的非阻塞等价物？

编辑:为了好奇,这里是一个使用原子整数作为守卫的有缺陷的尝试

private final AtomicInteger atomi = new AtomicInteger(0);
public Integer generateUniqueNegativeIdsWithAtomicAlgo() {
    boolean added = false;
    int result = 0;
    do {
        result = random.nextInt();
        if (result > 0) {
            result *= -1;
        }
        if (atomi.compareAndSet(0, result)) {
            added = cache.add(result);
        }   
    } while (!added);
    return atomi.getAndSet(0);
}

编辑:下面的测试工具:

public static void main(String[] args) {
    final int NUMBER_OF_THREADS = 10000;
    final Set uniques = Collections.synchronizedSet(new HashSet());
    final List positives = Collections.synchronizedList(new ArrayList());
    final NegativeUniqueIdGenerator nuig = new NegativeUniqueIdGenerator();
    Thread[] workers = new Thread[NUMBER_OF_THREADS];
    long start = System.nanoTime();
    for (int i = 0; i < workers.length; i++) {
        Runnable runnable = new Runnable() {
            public void run() {
                int number = nuig.generateUniqueNegativeIds();
                if (number > 0) {
                    positives.add(number);
                }
                uniques.add(number);
            }
        };
        workers[i] = new Thread(runnable);
        workers[i].start();
    }
    for (int i = 0; i < workers.length; i++) {
        try {
            workers[i].join();
        } catch (InterruptedException ie) {}
    }
    long end = System.nanoTime();
    System.out.println(String.format("duration = %dns", (end - start)));
    System.out.println(String.format("#threads = %d", NUMBER_OF_THREADS));
    System.out.println(String.format("#uniques = %d", uniques.size()));
    System.out.println(String.format("#positives = %d", positives.size()));
    System.out.println(String.format("#duplicates = %d", NUMBER_OF_THREADS - uniques.size()));
    System.out.println(String.format("ratio = %f",
            ((double) NUMBER_OF_THREADS - uniques.size())
                    / NUMBER_OF_THREADS));
    assert uniques.size() == NUMBER_OF_THREADS;
}

jpalecek.. 9

如果你不关心随机性,你可以减少一个计数器,如下所示:

private final AtomicInteger ai=new AtomicInteger(0);

public int nextID() {
  return ai.addAndGet(-1);
}

编辑:

对于随机数,您可以使用您的解决方案并使用例如.ConcurrentHashMap或ConcurrentSkipListSet而不是synchronizedSet.您必须确保不同的线程使用随机生成器的不同实例,并且这些生成器不相关.

如果你不关心随机性,你可以减少一个计数器,如下所示:

private final AtomicInteger ai=new AtomicInteger(0);

public int nextID() {
  return ai.addAndGet(-1);
}

编辑:

对于随机数,您可以使用您的解决方案并使用例如.ConcurrentHashMap或ConcurrentSkipListSet而不是synchronizedSet.您必须确保不同的线程使用随机生成器的不同实例,并且这些生成器不相关.

建议使用计数器的其他答案非常好,但如果非预测性(或至少是非平凡的可预测性)很重要,那么您的原始算法应该没问题.

为什么？

基本上,你得到一个重复整数的概率是非常(非常)(非常)小,大约1除以你还没有看到的整数的数量.如果您已经生成了N数字,则算法的预期运行时间近似为线性,N系数为1/2 ^ 32,这意味着您必须生成超过十亿个数字才能使预期运行时间超过2次迭代循环!在实践中,检查集合是否存在某个数字将会延长算法的运行时间,而不是重复循环的可能性(好吧,除非你使用了一个HashSet可能 - 我忘了它的渐近运行时是什么).

对于它的价值,确切的预期循环迭代次数是

2^64/(2^32 - N)^2

在您生成了一百万个数字后,这将达到1.00047 - 这意味着,例如,生成1,000,001到1,002,000个数字,在所有这些调用中,您可能会得到一个重复数字,总数.