当前位置: 首页 > 知识库问答 >
问题:

如果线程安全,是否有机会使并发性更强

有凯泽
2023-03-14

类AnagramGameDefault模拟一个字谜游戏。

submitScore()应该重新计算位置,得分最高的位置为1,同一位置上可以有多个球员。

public enum AnagramGameDefault{

INSTANCE;

private Map<String, Entry> leaderBoardUserEntryMap;

{
    leaderBoardUserEntryMap = new LinkedHashMap<>();
}

public int calculateScore(String word, String anagram) {

    if (word == null || anagram == null) {
        throw new NullPointerException("Both, word and anagram, must be non-null");
    }

    char[] wordArray = word.trim().toLowerCase().toCharArray();
    char[] anagramArray = anagram.trim().toLowerCase().toCharArray();

    int[] alphabetCountArray = new int[26];

    int reference = 'a';

    for (int i = 0; i < wordArray.length; i++) {
        if (!Character.isWhitespace(wordArray[i])) {
            alphabetCountArray[wordArray[i] - reference]++;
        }
    }
    for (int i = 0; i < anagramArray.length; i++) {
        if (!Character.isWhitespace(anagramArray[i])) {
            alphabetCountArray[anagramArray[i] - reference]--;
        }
    }

    for (int i = 0; i < 26; i++)
        if (alphabetCountArray[i] != 0)
            return 0;

    return word.length();

}

public void submitScore(String uid, int score) {

    Entry newEntry = new Entry(uid, score);
    sortLeaderBoard(newEntry);
}

private void sortLeaderBoard(Entry newEntry) {

    synchronized (leaderBoardUserEntryMap) {
        leaderBoardUserEntryMap.put(newEntry.getUid(), newEntry);

        // System.out.println("Sorting for " + newEntry);

        List<Map.Entry<String, Entry>> list = leaderBoardUserEntryMap.entrySet().stream()
                .sorted(Map.Entry.comparingByValue(Collections.reverseOrder())).collect(Collectors.toList());
        leaderBoardUserEntryMap.clear();

        int position = 0;
        int previousPosition = 0;
        int currentPosition = 0;

        for (Map.Entry<String, Entry> entry : list) {
            currentPosition = entry.getValue().getScore();
            if (!(currentPosition == previousPosition))
                position++;

            entry.getValue().setPosition(position);
            leaderBoardUserEntryMap.put(entry.getKey(), entry.getValue());

            previousPosition = currentPosition;

        }
    }

}

public List<Entry> getLeaderBoard(String uid) {

    final int maxEntriesAroundAnEntry = 2;

    if (!leaderBoardUserEntryMap.containsKey(uid))
        return Collections.emptyList();

    Entry userEntry = null;

    final List<Entry> leaderBoard = new ArrayList<>();
    List<Entry> lowerEntries = null;
    List<Entry> higherEntries = null;

    synchronized (leaderBoardUserEntryMap) {

        printBoard();

        userEntry = leaderBoardUserEntryMap.get(uid);
        int userPosition = userEntry.getPosition();
        int upperPosition = userPosition - maxEntriesAroundAnEntry;
        int lowerPosition = userPosition + maxEntriesAroundAnEntry;

        // Higher entries
        higherEntries = leaderBoardUserEntryMap.values().stream()
                .filter(entry -> (entry.getPosition() < userPosition && entry.getPosition() >= upperPosition))
                .map(entry -> new Entry(entry.getUid(), entry.getScore(), entry.getPosition()))
                .collect(Collectors.toList());

        // Lower entries
        lowerEntries = leaderBoardUserEntryMap.values().stream()
                .filter(entry -> (entry.getPosition() > userPosition && entry.getPosition() <= lowerPosition))
                .map(entry -> new Entry(entry.getUid(), entry.getScore(), entry.getPosition()))
                .collect(Collectors.toList());

        userEntry = new Entry(userEntry.getUid(), userEntry.getScore(), userEntry.getPosition());

        // }

        if (higherEntries != null && !higherEntries.isEmpty()) {

            if (higherEntries.size() >= maxEntriesAroundAnEntry) {
                higherEntries = higherEntries.subList(higherEntries.size() - maxEntriesAroundAnEntry,
                        higherEntries.size());
            }

            leaderBoard.addAll(higherEntries);
        }

        leaderBoard.add(userEntry);

        if (lowerEntries != null && !lowerEntries.isEmpty()) {

            if (lowerEntries.size() >= maxEntriesAroundAnEntry) {
                lowerEntries = lowerEntries.subList(0, maxEntriesAroundAnEntry);
            }

            leaderBoard.addAll(lowerEntries);
        }
    }

    return leaderBoard;
}

public void printBoard() {

    System.out.println("---------Start : Current leader board---------");
    leaderBoardUserEntryMap.forEach((key, value) -> {
        System.out.println("BOARD ENTRY : " + key + " : " + value);
    });
    System.out.println("---------End : Current leader board---------");
}

}
public class Entry implements Comparable<Entry> {

    private String uid;
    private int score;
    private int position;

    public Entry(String uid, int score) {

        this.uid = uid;
        this.score = score;

    }

    public Entry(String uid, int score, int position) {

        this.uid = uid;
        this.score = score;
        this.position = position;
    }

    public Entry() {

    }

    public String getUid() {
        return uid;
    }

    public void setUid(String uid) {
        this.uid = uid;
    }

    public int getScore() {
        return score;
    }

    public void setScore(int score) {
        this.score = score;
    }

    public int getPosition() {
        return position;
    }

    public void setPosition(int position) {
        this.position = position;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + score;
        result = prime * result + ((uid == null) ? 0 : uid.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Entry other = (Entry) obj;
        if (score != other.score)
            return false;
        if (uid == null) {
            if (other.uid != null)
                return false;
        } else if (!uid.equals(other.uid))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Entry [uid=" + uid + ", score=" + score + ", position=" + position + "]";
    }

    @Override
    public int compareTo(Entry o) {
        // TODO Auto-generated method stub
        if (o == null)
            return -1;

        return Integer.compare(score, o.getScore());
    }

}

tester类:

public class AnagramGameDefaultDemo {

    public static void main(String[] args) {

        if (args == null || args.length < 1) {
            System.out.println("Enter testing approach - 1 for single threaded, 2 for multi-threaded");
            return;
        }

        switch (args[0]) {

        case "1": {
            new AnagramGameDefaultDemo().testSingleThreaded();
            break;
        }

        case "2": {
            new AnagramGameDefaultDemo().testMultithreaded();
            break;
        }

        default: {
            System.out.println("Enter proper option(1 or 2)");
            break;
        }
        }

    }

    private void testMultithreaded() {

        Map<String, String> stringAnagramMap = new HashMap<>();

        CountDownLatch countDownLatchOne = new CountDownLatch(1);

        stringAnagramMap.put("raw", "war");
        stringAnagramMap.put("raw", "wars");
        AnagramGamePlayer jake = new AnagramGamePlayer("jake", stringAnagramMap, countDownLatchOne);
        new Thread(jake, "jake").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("tool", "loot");
        AnagramGamePlayer ace = new AnagramGamePlayer("ace", stringAnagramMap, countDownLatchOne);
        new Thread(ace, "ace").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("William Shakespeare", "I am a weakish speller");
        AnagramGamePlayer max = new AnagramGamePlayer("max", stringAnagramMap, countDownLatchOne);
        new Thread(max, "max").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("School master", "The classroom");
        AnagramGamePlayer tBone = new AnagramGamePlayer("tBone", stringAnagramMap, countDownLatchOne);
        new Thread(tBone, "tBone").start();

        stringAnagramMap.clear();

        countDownLatchOne.countDown();

        CountDownLatch countDownLatchTwo = new CountDownLatch(1);

        stringAnagramMap.put("Punishments", "Nine Thumps");
        AnagramGamePlayer razor = new AnagramGamePlayer("razor", stringAnagramMap, countDownLatchTwo);
        new Thread(razor, "razor").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("Dormitory", "Dirty Room");
        AnagramGamePlayer chip = new AnagramGamePlayer("chip", stringAnagramMap, countDownLatchTwo);
        new Thread(chip, "chip").start();

        stringAnagramMap.clear();

        countDownLatchTwo.countDown();

        CountDownLatch countDownLatchThree = new CountDownLatch(1);

        stringAnagramMap.put("Mother in law", "Hitler woman");
        AnagramGamePlayer dale = new AnagramGamePlayer("dale", stringAnagramMap, countDownLatchThree);
        new Thread(dale, "dale").start();

        countDownLatchThree.countDown();

        stringAnagramMap.clear();
    }

    private final class AnagramGamePlayer implements Runnable {

        private Map<String, String> stringAnagramMap = new HashMap<>();
        private String uid;
        private CountDownLatch countDownLatch;

        public AnagramGamePlayer(String uid, Map<String, String> stringAnagramMap, CountDownLatch countDownLatch) {
            this.stringAnagramMap.putAll(stringAnagramMap);
            this.uid = uid;
            this.countDownLatch = countDownLatch;
        }

        @Override
        public void run() {
            AnagramGameDefault anagramGameDefault = AnagramGameDefault.INSTANCE;

            try {
                countDownLatch.await();
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }

            System.out.println("Player " + uid + " started playing with " + stringAnagramMap);
            stringAnagramMap.entrySet().forEach(entry -> {
                anagramGameDefault.submitScore(uid,
                        anagramGameDefault.calculateScore(entry.getKey(), entry.getValue()));
                printLeaderBoard(uid, anagramGameDefault.getLeaderBoard(uid));

            });

            System.out.println("Player " + uid + " completed playing");
        }

    }

    private void testSingleThreaded() {
        AnagramGameDefault anagramGameDefault = AnagramGameDefault.INSTANCE;
        anagramGameDefault.submitScore("Jake", 3);
        anagramGameDefault.submitScore("Ace", 7);
        anagramGameDefault.submitScore("Max", 1);
        anagramGameDefault.submitScore("T-Bone", 14);
        anagramGameDefault.submitScore("Razor", 6);
        anagramGameDefault.submitScore("Razor", 7);
        anagramGameDefault.submitScore("He-Man", 4);
        anagramGameDefault.submitScore("Men-at-Arms", 8);
        anagramGameDefault.submitScore("BattleCat", 3);
        anagramGameDefault.submitScore("Jake", 2);
        anagramGameDefault.submitScore("BattleCat", 3);
        anagramGameDefault.printBoard();

        anagramGameDefault.submitScore("Men-at-Arms", 21);
        anagramGameDefault.submitScore("Orko", 20);
        anagramGameDefault.submitScore("Jake", 4);
        anagramGameDefault.printBoard();

        System.out.println();
        printLeaderBoard("user5", anagramGameDefault.getLeaderBoard("user5"));
        System.out.println();
        printLeaderBoard("user4", anagramGameDefault.getLeaderBoard("user4"));
        System.out.println();
        printLeaderBoard("user15", anagramGameDefault.getLeaderBoard("user15"));
        System.out.println();
        List<Entry> entries = anagramGameDefault.getLeaderBoard("user1");
        printLeaderBoard("user1", entries);

        System.out.println("Changing state of the received entries");
        entries.forEach(entry -> {
            entry.setPosition(1);
            entry.setScore(0);
        });

        anagramGameDefault.printBoard();
        printLeaderBoard("user1", anagramGameDefault.getLeaderBoard("user1"));
    }

    private static void printLeaderBoard(String user, List<Entry> leaderBoard) {

        if (user == null || leaderBoard.isEmpty()) {
            System.out.println("Either user " + user + " doesn't exist or leader board is empty " + leaderBoard);
        }

        System.out.println("**********Printing leader board for " + user);
        leaderBoard.forEach(System.out::println);
        System.out.println("**********");
    }

}

共有1个答案

刁钧
2023-03-14

似乎整个过程中唯一的共享状态是leaderboarduserentrymap。在sortleaderboard中更新时,您将在其上进行同步。在GetLeaderBoard中,由于某种原因,在检查if(!LeaderBoardUserEntryMap.ContainsKey(uid))时,您尚未对其进行同步。那是次要的,但你也应该这样做。稍后,您在构建leader Board时对其进行同步。

从这个角度来看,您的同步似乎是足够的。

我发现有点问题的是,您的entry是可变的,并且存储position。这使得您的更新操作更加成问题。您必须在每次更新时重新排序和重新设置位置。并且您正在锁定所有其他更新甚至读取操作。我会避免多线程代码中的可变对象

然而,这不会有多大帮助,因为您的“检索”逻辑(围绕目标条目创建leader board)并不是那么简单,需要多次读取。所以我认为最好不要使用并发集合,而是在集合上进行同步,并使更新和检索尽可能紧凑。如果您放弃在条目中包含位置的想法,那么update就是一个简单的添加。那么您只需要尽可能快地读取条目周围的条目(在synchronized块内)。这对于树集来说应该是相当快的。

 类似资料:
  • 问题内容: 我一直在假设线程安全也不是线程安全,但是在最近的一次讨论中,一位同事告诉我线程安全。 因此,我做了一些研究,却一无所获。很多人认为它是线程安全的,很多人认为它不是线程安全的。而且,最重要的是,文档没有以一种或另一种方式说任何话,不是为了,甚至不是。 那是什么呢? 问题答案: 这是指向Java 7 中Calendar和GregorianCalendar的源代码的链接。 如果阅读该代码,您

  • tcp套接字是具有双向读写功能的endpoint。在java中,我们可以获得套接字的InputStream和OutputStream。 同时使用这些流是否安全? 据我所知,有一个连接能够在任何给定时间从一个endpoint发送或接收到其他数据。 我正在基于SocketChannels实现nio传输层,我想保留一个线程用于所有写入,一个线程用于接受和读取,但我不确定如果我的线程同时尝试在同一个套接字

  • 假设: 只有一个特定的线程设置了某个引用字段(不是长或双精度,所以写入它是原子的) 有任意数量的线程可能会读取同一个字段 稍微陈旧的读取是可以接受的(最多几秒钟) 在这种情况下,您需要挥发性或原子参考或类似的东西吗? 该条指出: 如果您严格遵守单一写入器原则,则不需要内存障碍。 这似乎表明,在我描述的情况下,你真的不需要做任何特殊的事情。 我做了一个测试,结果很奇怪: 有时运行this会输出“线程

  • 问题内容: 我的应用程序中有多个线程同时访问BitSet。该文档说: 如果没有外部同步,则BitSet对于多线程使用是不安全的。 它没有说读或写是否不安全。谁能解释。 问题答案: 仅当初始化的最后一个操作与读取该操作的操作之间存在“先于”关系时,A 对于只读操作才是安全的。 最简单的方法是使用。例如: 这足以确保“安全发布”。 但是,如果您不执行此类操作,则无法保证读取的线程将看到完全初始化的状态

  • 1.1 定义 线程安全:当多个线程访问某个类时,不管运行时环境采用何种调度方式或者这些线程将如何交替执行,并且在主调代码中不需要任何额外的同步或协调,这个类都能表现出正确的行为,那么就称这个类是线程安全的。 线程不安全:如果一个类对象同时可以被多个线程访问,如果不做同步处理,可能表现出线程不安全现象(抛出异常、逻辑错误)。 1.2 原子性 1.2.1 定义提供了互斥访问,同一时刻(时间段)只能有一

  • 我有一个在Oracle 11g DB上运行的insert语句,如下所示: 这里有一个处理PostgreSQL的类似问题。但是,由于Oracle序列由所有会话共享,所以我不能相信DB会给出当前会话中最后插入的值。