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

https://stackoverflow.com/questions/579925

06-09-2019
|

题

我最近重构了一段用于生成唯一负数的代码。
编辑： 多个线程获取这些 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;
}

上面的代码结构，及其对集合和“重试”循环的推测性添加，让我认为存在一个等效的非阻塞算法，可以用任何以下内容替换同步集合原子变量.

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

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

编辑： 出于好奇，这是一个使用原子整数作为保护的有缺陷的尝试

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;
}

解决方案

这是你给的要求，我个人只是用一种中等质量的随机数生成器，你知道你需要的唯一号码的数量之内不会产生重复。除非你有没有提到一个额外的要求，似乎矫枉过正保持在设定的所有先前生成的数字。

例如，使用一个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;
  }

其他提示

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

private final AtomicInteger ai=new AtomicInteger(0);

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

编辑：

有关的随机数，你可以用你的解决方案，并使用如。的ConcurrentHashMap或ConcurrentSkipListSet代替synchronizedSet。你必须保证不同线程使用随机生成器的不同实例，并且这些发电机是不相关的。

其他答案用计数器这表明是优秀的，但如果nonpredictability（或至少，平凡的可预见性）的是的重要，原来的算法应该就好了。

为什么？

基本上，你会得到一个重复整数的概率是非常非常（非常）（非常）小，大致1由你还没有看到整数的个数分割。如果你已经产生N号码，该算法的运行时间预计在N近似为线性，以1/2 ^ 32的系数，这意味着你将不得不产生超过十亿的数字只是为了获得预期的运行时间超过2个迭代循环！在实践中，检查一定数量存在的集将做更多伸出你的算法的运行时间比重复循环（当然，除非您使用的是HashSet可能的可能性 - 我忘记了它的渐近运行时间是）。

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

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

您已经生成一个万个号码后，该工程以1.00047 - 这意味着，比如说，生成第百万零一到1,002,000th数字，你可能会得到的一个的重复次数，< EM>总，在所有这些呼叫。

对于所有列出的要求优雅的溶液，据我所知，只是递减从-1开始的值。我怀疑，但是，你有没有列出的所有要求。

尝试这种情况： http://www.javaconcurrencyinpractice.com/listings.html

我将在OP的答案与jpalecek的组合给出：

private final AtomicInteger ai=new AtomicInteger(0);

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

在高规模LIB具有NonBlockingHashSet您可以使用。只是NonBlockingHashSet的实例来替换你的设置实例，你都设置。

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

我觉得你的意思是非阻塞和折返。

编辑：（代替我原来的，因为这是好多了）

这实际上是相当高性能的基于线程的选项只是浮现在脑海（至少比原来的更好的性能）。如果你创建了一个弱哈希映射一个线程对象的“重点”和“值”把一个物体制造了一系列的，比如，1000个号码从特定范围的能力。

这样可以为每个线程它自己的1000号范围从分配。当对象用完的数字，有它返回一个无效的数字（0？），你会知道，你必须分配一个新的范围到该对象。

有将任何地方不同步的任何东西（编辑：哎呦，还是一个小错误见下文），弱哈希映射将被销毁（无需特别维护），并自动释放线程最慢的部分将是一个哈希查找的螺纹这实际上是非常快的。

获取当前正在运行的线程同：

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;
    }
}

它只是让我吃惊的是，一个大的同步块，而不是可以通过2个上的不同对象的同步非常小的，一个用于“+ =计数”和一个用于。把（）来代替。如果冲突仍在放慢你失望，这可能帮助（虽然如果冲突仍在放慢你失望（真的???）你会得到更好的服务只是提高计数。

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow