- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
对于我正在研究的算法,我尝试开发一种黑名单机制,可以以特定方式将数组列入黑名单:如果“1、2、3”被列入黑名单,“1、2、3、4、5”也被列入黑名单被列入黑名单。
我对到目前为止提出的解决方案感到非常满意。但是当我从多个线程访问黑名单时,似乎存在一些严重的问题。 “包含”方法(参见下面的代码)有时会返回 true,即使数组未列入黑名单。如果我只使用一个线程就不会出现这个问题,所以很有可能是并发问题。
我试过添加一些同步,但它没有改变任何东西。我还使用 java.util.concurrent 类尝试了一些略有不同的实现。关于如何解决此问题的任何想法?
public class Blacklist {
private static final int ARRAY_GROWTH = 10;
private final Node root = new Node();
private static class Node{
private volatile Node[] childNodes = new Node[ARRAY_GROWTH];
private volatile boolean blacklisted = false;
public void blacklist(){
this.blacklisted = true;
this.childNodes = null;
}
}
public void add(final int[] array){
synchronized (root) {
Node currentNode = this.root;
for(final int edge : array){
if(currentNode.blacklisted)
return;
else if(currentNode.childNodes.length <= edge) {
currentNode.childNodes = Arrays.copyOf(currentNode.childNodes, edge + ARRAY_GROWTH);
}
if(currentNode.childNodes[edge] == null) {
currentNode.childNodes[edge] = new Node();
}
currentNode = currentNode.childNodes[edge];
}
currentNode.blacklist();
}
}
public boolean contains(final int[] array){
synchronized (root) {
Node currentNode = this.root;
for(final int edge : array){
if(currentNode.blacklisted)
return true;
else if(currentNode.childNodes.length <= edge || currentNode.childNodes[edge] == null)
return false;
currentNode = currentNode.childNodes[edge];
}
return currentNode.blacklisted;
}
}
最佳答案
编辑:我通过一个包含十个线程的测试套件运行了您的代码,添加并比较了数千个模式,但我没有发现您的实现有任何问题。我相信你误解了你的数据。例如,在线程环境中,这有时会返回 false:
// sometimes this can be false
blacklist.contains(pattern) == blacklist.contains(pattern);
另一个线程在第一次调用之后和第二次调用之前更改了黑名单。这是正常行为,类本身无法阻止它。如果这不是您想要的行为,您可以从类外部同步它:
synchronized (blacklist) {
// this will always be true
blacklist.contains(pattern) == blacklist.contains(pattern);
}
原始回复:您同步了根节点,但这并没有同步它的任何子节点。要使您的类防弹,您要做的就是同步 add(int[])
和 contains(int[])
方法,然后不要泄漏任何引用。这可确保一次只能有一个线程使用黑名单对象。
我在试图理解它的同时摆弄了你的代码,所以你最好拥有它:
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class Blacklist {
private final Node root = new Node(Integer.MIN_VALUE, false);
public synchronized void add(int[] array) {
if (array == null) return;
Node next, cur = root;
for(int i = 0; i < array.length-1 && !cur.isLeaf(); i++) {
next = cur.getChild(array[i]);
if (next == null) {
next = new Node(array[i], false);
cur.addChild(next);
}
cur = next;
}
if (!cur.isLeaf()) {
next = cur.getChild(array[array.length-1]);
if (next == null || !next.isLeaf())
cur.addChild(new Node(array[array.length-1], true));
}
}
public synchronized boolean contains(int[] array) {
if (array == null) return false;
Node cur = root;
for (int i = 0; i < array.length; i++) {
cur = cur.getChild(array[i]);
if (cur == null) return false;
if (cur.isLeaf()) return true;
}
return false;
}
private static class Node {
private final Map<Integer, Node> children;
private final int value;
public Node(int _value, boolean leaf) {
children = (leaf?null:new HashMap<Integer, Node>());
value = _value;
}
public void addChild(Node child) { children.put(child.value, child); }
public Node getChild(int value) { return children.get(value); }
public boolean isLeaf() { return (children == null); }
}
}
Collections framework可以让您轻松很多。重新实现 ArrayList 不会给自己带来任何好处。
这里我使用了一个 HashMap 这样你就不必为这样的东西分配超过 9000 个引用:
blacklist.add(new int[] {1, 2000, 3000, 4000});
关于java - 数组的并发问题(Java),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2936049/
我正在尝试在多线程环境中实现某种累积逻辑;我想知道没有 lock 和 synchronized 关键字是否有更好/更快的方法来做到这一点?以下是我当前的代码: public class Concurr
我需要帮助构建一个实现信号量的监视器,简单的 C 示例就可以。 这是为了证明可以在任何可以使用信号量的地方使用监视器。 最佳答案 如果您说允许使用互斥锁/condvars,请检查: #include
我已经构建了一些返回部分产品目录的 ajax,并且我正在尝试将 xml 输出到文档中,到目前为止,这是我所拥有的: $("#catalog").append("Item NamePriceDe
很抱歉,如果我的问题之前已经被问过,或者它太明显了,但我真的需要澄清这一点。感谢您的帮助。 在多用户界面中,如果来自不同用户的相同事务同时到达服务器,会发生什么? 我有下一张表: create tab
这可能是一个愚蠢的问题,但是这个程序的输出(它的方式)可以为零吗? public class Test2{ int a = 0; AtomicInteger b = new Atomi
假设我本地主机上的一个网站处理每个请求大约需要 3 秒。这很好,正如预期的那样(因为它在幕后进行了一些奇特的网络)。 但是,如果我在选项卡(在 firefox 中)中打开相同的 url,然后同时重新加
我对 MongoDB 的读锁定有点困惑。单个集合可以支持多少个并发读取操作? 最佳答案 如 tk 给出的链接中所写:http://www.mongodb.org/pages/viewpage.acti
如果有四个并发的 CUDA 应用程序在一个 GPU 中竞争资源会发生什么这样他们就可以将工作卸载到图形卡上了? Cuda Programming Guide 3.1 提到那里 某些方法是异步的: 内核
👊上次的百度面试遇到了关于spark的并发数的问题,今天我们就来将这些问题都一并解决一下,图画的的有点丑,还行大家见谅,百度实习的问题我放在了下面的链接👇: 链接: 2022百度大数据开发工程师实
我对 Groovy 线程有疑问。 我的任务是以某种方式翻译给定目录中的每个文件 并将生成的输出放在其他目录中的文件中。 我编写了以下代码,该代码有效: static def translateDir(
Java中的同步和锁定有什么区别? 最佳答案 synchronized是语言关键字;锁是对象。 当一个方法或代码块被标记为同步时,您是说该方法或代码块必须先获得某个锁对象(可以在同步的语法中指定)才能
我需要创建一个能够同时处理来自客户端的多个请求的并发 RPC 服务器。 使用 rpcgen linux编译器(基于sun RPC),不支持-A为并发服务器创建 stub 的选项。 (-A 选项在 so
System.out.println("Enter the number of what you would like to do"); System.out.println("1 = Manuall
我正在将我的应用程序移植到 iOS 8.0 并注意到 UIAlertView 已被弃用。 所以我改变了使用 UIAlertController 的方法。这在大多数情况下都有效。 除了,当我的应用程序打
我正在逐行同时读取两个文本文件。 我特别想做的是当lineCount在每个线程上都是相同的我想看看扫描仪当前正在读取的字符串。 我环顾四周寻找可以实现的某些模式,例如 Compare and Swap
我正在阅读 Java Concurrency in Practice .在章节中断政策部分 取消和关闭 它提到 A task should not assume anything about the
我正在尝试学习线程,互斥等的基础知识。遵循here的文档和示例。在下面的代码中,我得到预期的输出。问题: 想确认我是否有任何陷阱?我们如何改善下面的代码? 我的线程在哪一行尝试获取互斥锁或正在等待互斥
并发是指两个任务在不同的线程上并行运行。但是,异步方法并行运行,但在同一个线程上。这是如何实现的?另外,并行性怎么样? 这三个概念有什么区别? 最佳答案 并发和并行实际上与您正确推测的原理相同,两者都
以此ConcurrentDouble类定义为例: public class ConcurrentDouble { public double num = 0; public void subt
在得知并发确实增加了许多人的吞吐量后,我一直计划在项目中使用并发。现在我在多线程或并发方面还没有做太多工作,因此决定在实际项目中使用它之前学习并进行简单的概念验证。 以下是我尝试过的两个示例: 1.
我是一名优秀的程序员,十分优秀!