gpt4 book ai didi

java - 数组的并发问题(Java)

转载 作者:搜寻专家 更新时间:2023-11-01 03:45:11 25 4
gpt4 key购买 nike

对于我正在研究的算法,我尝试开发一种黑名单机制,可以以特定方式将数组列入黑名单:如果“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/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com