Top N

The top ranking is very common in actual work, such as the top 10 abnormal information in the business system or the top 5 cities according to the number of people who enter Xi ‘an during the epidemic.

Top model

Common models exist in the form of KV. K is the statistical dimension and is ranked according to V.

Designed and implemented

The information is stored in the memory, and the clearing policy is provided. For Top N, all the information is cleared after N. For the sake of performance, when storing information, no special processing is done to ensure that information can be stored quickly, and asynchronous processing is used to support high concurrency. The sorting function is realized in the message cleaning mechanism, and all the sorting is cleaned after N.

Information storage implementation

   /** Basic information */
   private static final int MAX_RECODER = 100;

    private static ConcurrentHashMap<String, Message> topMessage = new ConcurrentHashMap<>();

    private static Lock lock = new ReentrantLock();
	/** Demo creates a thread pool in this way. It is better to create a thread pool in another way
    private static ExecutorService executorService = Executors.newSingleThreadExecutor(new ThreadFactoryBuilder().setNameFormat("Top100-thread-%d").build());

    private static ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor(new ThreadFactoryBuilder().setNameFormat("Top100-Recycle-thread-%d").build());

Copy the code

If the concurrency of statistics is high, the thread pool can be increased.

    public static void addMessage(String message) {
        executorService.execute(() -> {
            add(message);
        });
    }

    private static void add(String message) {
        Message obj = topMessage.get(message);
        if (null == obj) {
            if (lock.tryLock()) {
                try {
                    obj = new Message();
                    obj.setMessage(message);
                } finally{ lock.unlock(); }}else {
                while (null == obj) {
                    obj = topMessage.get(message);
                }
            }
        }
        obj.incount();
        topMessage.put(message, obj);
    }
Copy the code

Cleanup policy implementation

A scheduled task is used to clear data periodically, avoiding the need to clear data every time when the number of concurrent tasks is high

  /** Clean up every 5 seconds */  
  public static void recyleSchedule(a) {
        scheduledExecutorService.scheduleAtFixedRate(() -> {
            recycle();
        }, 0.5, TimeUnit.SECONDS);
    }   
	/** Batch clean */
    private static void recycle(a) {
        if (topMessage.size() > MAX_RECODER) {
            ConcurrentHashMap<String, Message> copyMap = new ConcurrentHashMap<>();
            SortedSet<Message> sortedSet = new TreeSet<>(topMessage.values());
            sortedSet.forEach(x -> {
                copyMap.put(x.getMessage(), x);
                if (copyMap.size() >= MAX_RECODER) {
                    return; }}); topMessage = copyMap; }}Copy the code

Access to information

    // Get the top information
    public static Collection<Message> getTop(int top) {
        return getAny(top);
    }

    // Get all the information
    public static Collection<Message> getAll(a) {
        return getAny(MAX_RECODER);
    }

    private static Collection<Message> getAny(int top) {
        List<Message> result = new ArrayList<>();
        SortedSet<Message> sortedSet = new TreeSet<>(topMessage.values());
        sortedSet.forEach(x -> {
            result.add(x);
            if (result.size() >= top) {
                return; }});return result;
    }
Copy the code

Messge is an encapsulation of a message

    static class Message implements Comparable<Message> {

        private String message;

        private volatile int count = 0;

        public void setMessage(String message) {
            this.message = message;
        }

        private void incount(a) {
            count++;
        }

        public String getMessage(a) {
            return message;
        }

        public int getCount(a) {
            return count;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Message) {
                return this.compareTo((Message) obj) == 0;
            }
            return super.equals(obj);
        }

        @Override
        public int compareTo(Message o) {
            if (o == null || o.getMessage() == null) {
                return -1;
            }
            if (o.getCount() - this.getCount() == 0) {
                return 0;
            }
            return (o.getCount() - this.getCount()); }}Copy the code

At the end

The above is a personal solution to the needs of top class. If you have a better solution, we can discuss together.