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

Question

我最近重构了一段用于生成唯一负数的代码。
编辑：多个线程获取这些ID并将其作为关键字添加到数据库;数字需要是负数才能容易识别 - 在测试会话结束时，他们将从数据库中删除。

我的Java算法是这样的：上面

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

的代码结构，其投机除了一套和“重试”循环，让我觉得有它取代了同步设置具有等效非阻塞算法任何atomic variables。

我做了几次尝试使用原子变量重新编写代码，但都未通过多线程攻击测试。

有没有优雅的无阻塞等效物？

编辑：为了好奇这里是用原子整数作为后卫

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<Integer> uniques = Collections.synchronizedSet(new HashSet<Integer>()); 
    final List<Integer> positives = Collections.synchronizedList(new ArrayList<Integer>()); 
    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; 
} 

Answer 1

根据您提出的要求，我个人只会使用一个中等质量的随机数字生成器，您不会在需要的唯一数字的数量内生成重复数据。除非你有一个额外的要求，你没有提到，看起来矫枉过正保留了以前生成的所有数字。

例如，使用32位XORShift生成器将在重复模式之前以“随机”顺序生成所有2^31个负4字节整数。如果你需要更多的数字，你可能不希望把它们放在哈希集合中。所以像这样的东西（警告：没有头的未经测试的代码...）：

int seed = (int) System.nanoTime(); 
final int origSeed = seed; 

public int nextUniqueNegativeNumber() { 
    int n = seed; 
    do { 
    n ^= (n << 13); 
    n ^= (n >>> 17); 
    n ^= (n << 5); 
    seed = n; 
    if (n == origSeed) { 
     throw new InternalError("Run out of numbers!"); 
    } 
    } while (n > 0); 
    return n; 
} 

我将留给读者来转换“种子”如果并发是必须使用的AtomicInteger ...

编辑：实际上，以优化您的并发情况下，也许只有想要在获得下一个负数号码后写回“种子”。

OK，大众的需求，原子的版本将随后是这样的：

AtomicInteger seed = new AtomicInteger((int) System.nanoTime()); 

    public int nextUniqueNegativeNumber() { 
    int oldVal, n; 
    do { 
     do { 
     oldVal = seed.get(); 
     n = oldVal^(oldVal << 13); // Added correction 
     n ^= (n >>> 17); 
     n ^= (n << 5); 
     } while (seed.getAndSet(n) != oldVal); 
    } while (n > 0); 
    return n; 
    } 

Answer 2

列出的所有优雅的解决方案就我所知，要求只是从-1开始递减一个值。不过，我怀疑你没有列出所有要求。

Answer 3

如果你不关心的随机性，你可以递减计数器，就像这样：

private final AtomicInteger ai=new AtomicInteger(0); 

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

编辑：

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

Answer 4

我认为你的意思是非阻塞和可重入。

编辑：（取代原来的我，因为这是更好）

，实际上是相当高性能的基于线程的选项只是浮现在脑海（至少比原来的更好的性能）。如果你创建了一个带有线程对象的弱哈希映射作为“Key”，并且“Value”将对象放入一个能够从一个特定范围内制造一系列1000个数字的对象。

通过这种方式，您可以为每个线程分配自己分配的1000个号码范围。当对象用完数字时，让它返回一个无效数字（0？），并且您将知道必须为该对象分配一个新范围。 （编辑：whoops，有点不对，见下文），弱散列映射会自动释放被破坏的线程（无需特殊维护），最慢的部分将是单个散列查找实际上非常快的线程。

获得当前正在运行的线程有：

Thread currThread=Thread.getCurrentThread(); 

我也可能是错的，你可能只需要进行同步的方法，那么这会工作：

int n=-1; 
synchronized int getNegativeNumber() { 
    return n--; 
} 

我继续写它（有时这些东西卡在我的头上，直到我做到了，只要我做了它，我不妨发布它）。未经测试和所有，但我敢肯定，它应该是关闭，如果没有开箱即用。只需一个静态方法调用一个类来获得唯一的负数。 （哦，我确实需要一些同步，但只会使用0.001％的时间）。

希望有一种方法来创建一个链接的代码块，而不是像这样内联，而不会离开网站 - 关于长度的抱歉。

package test; 

import java.util.WeakHashMap; 

public class GenNumber { 
    // Static implementation goes first. 
    private static int next = -1; 
    private static final int range = 1000; 

    private static WeakHashMap<Thread, GenNumber> threads = new WeakHashMap<Thread, GenNumber>(); 

    /** 
    * Generate a unique random number quickly without blocking 
    * 
    * @return the random number < 0 
    */ 
    public static int getUniqueNumber() { 
     Thread current = Thread.currentThread(); 
     int next = 0; 

     // Have to synchronize some, but let's get the very 
     // common scenario out of the way first without any 
     // synchronization. This will be very fast, and will 
     // be the case 99.9% of the time (as long as range=1000) 
     GenNumber gn = threads.get(current); 
     if (gn != null) { 
      next = gn.getNext(); 
      if (next != 0) 
       return next; 
     } 

     // Either the thread wasn't found, or the range was 
     // used up. Do the rest in a synchronized block. 
     // The three lines tagged with the comment "*" have 
     // the potential to collide if this wasn't synchronized. 
     synchronized (threads) { 
      if (gn == null) { 
       gn = new GenNumber(next -= range); // * 
       threads.put(current, gn); // * 
       return gn.getNext(); // can't fail this time 
      } 
      // now we know the range has run out 

      gn.setStart(next -= range); // * 
      return gn.getNext(); 
     } 
    } 

    // Instance implementation (all private, nobody needs to see this) 
    private int start; 
    private int count; 

    private GenNumber(int start) { 
     setStart(start); 
    } 

    private int getNext() { 
     if (count < range) 
      return start - count; 
     return 0; 
    } 

    private GenNumber setStart(int start) { 
     this.start = start; 
     return this; 
    } 
} 

它只是让我吃惊，而不是一个大的synchronized块可以由2分不同的对象同步非常小的，一为“+ =计数”，一个是。把更换（）。如果碰撞仍在减慢你的速度，那可能会有帮助（虽然如果碰撞仍在减慢你的速度（真的吗？）你会更好地服务，只是提高计数。

Answer 5

其他答案建议使用计数器是优秀的，但如果nonpredictability（或至少，平凡的可预见性）是重要的是，你原来的算法应该是蛮好的。

为什么？

基本上，你会得到一个重复的整数的概率是非常非常（非常）非常小，大概是1除以你尚未见过的整数的数目如果你已经产生了N个数字，该算法的预期运行时间在N中近似线性，系数为1/2^32，这意味着您必须生成超过10亿个数字才能使预期运行时间超过循环的2次迭代！在实践中，检查集合是否存在某个数字将会做更多的事情来扩展算法的运行时间，而不是重复循环的可能性（当然，除非你使用了一个HashSet也许 - 我忘记了它的渐近运行时间是）。

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

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

您已经生成后万个号码，这个工程以1.00047 - 这意味着，比如说，生成第一百万○一到第100万个数字，在所有这些调用中，您可能会得到一个重复编号，总计。

Answer 6

试试这个：http://www.javaconcurrencyinpractice.com/listings.html

Answer 7

我将在OP的回答结合起来jpalecek的给予：

private final AtomicInteger ai=new AtomicInteger(0); 

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

Answer 8

高规模的lib有一个可以使用的NonBlockingHashSet。只需将您的设置实例替换为NonBlockingHashSet的一个实例，即可完成设置。

http://sourceforge.net/projects/high-scale-lib