Retrieve fixed number of entries around an entry in a map sorted by values

Question

The POJO viz. Entry.java represents an entry in the leaderboard. Position is the position in the leaderboard, 1 being the user with the highest score

public class Entry {

    private String uid;
    private int score;
    private int 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;

        if (!(obj instanceof Entry))
            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 + "]";
    }
}

These entries are stored in a Map in a class as shown below :

public class GameDefault {

Map<String, Entry> leaderBoardUserEntryMap;

public void submitScore(String uid, int score) {

        Entry newEntry = new Entry(uid, score);
        leaderBoardUserEntryMap.put(uid, newEntry);
    }

public List<Entry> getLeaderBoard(String uid) {

    /* Option-3 : A Map of uid-Entry */
    leaderBoardUserEntryMap.entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.comparing(Entry::getScore, Integer::compare).reversed()))
                .filter(/*What to put here*/);

        return null;
    }
}

The method getLeaderBoard() is supposed to return

max two entries that have larger score than the user (the users that are immediately above the user in the leaderboard), the user’s own entry and max two entries that are immediately after the user in the leaderboard

.

I couldn't figure out the predicate to use to return exactly 5 entries, including the one being searched for. Another aspect is performance since the leaderBoard can have hundreds of thousands of entries.

**********Edit-1**********

The following snippet provided by @nullpointer does the trick but I have some points on my mind

List<GameEntry> selectedEntries =  leaderBoardUserEntryMap.entrySet().stream()
            .sorted(Map.Entry.comparingByValue(Comparator.comparing(GameEntry::getScore, Integer::compare)
                    .reversed())).map(Map.Entry::getValue).collect(Collectors.toList());

int indexOfnewEntry = selectedEntries.indexOf(leaderBoardUserEntryMap.get(uid));
return  selectedEntries.subList(indexOfnewEntry-2,indexOfnewEntry+2);

Note : The leaderBoardUserEntryMap can have millions of entries

The indexOfnewEntry and +- 2 can cause IndexOutOfBoundsException, guarding against it seems a bit tedious, any optimal ways here?
Will using parallelStream() cause problems ?

List entries = leaderBoardUserEntryMap.entrySet().parallelStream().sorted(Map.Entry.comparingByValue(Comparator.comparing(Entry::getScore, Integer::compare).reversed())).parallel(). map(Map.Entry::getValue).collect(Collectors.toList());

If I understand you correctly, you are trying to return a list of 5 elements of the top players using your custom comparator! Have you tried.limit(5) method on your stream — Ahmad Sanie, Sep 12 '17 at 09:41
P.s you don't need a filter since you are returning a sorted stream ! You just need to limit the number of retrieved elements to 5 and then use a collector to return a list. Let me know if you got it ; if not i can add an answer; cheers — Ahmad Sanie, Sep 12 '17 at 09:46
Nopes, it not top 5 entries. While the collection should be sorted by score descending, find an entry pertaining to a uid and then retrieve 2 above and 2 below and return all 5. Check @yogesh 's comments on the answer — Kaliyug Antagonist, Sep 12 '17 at 10:14

Naman · Accepted Answer · 2017-09-12T14:35:04.447

1

Stream#limit shall help you restrict finding the top N(5) users on the reversed list you've created and further you can map List> using the values and collect a List<Entry> from it finally as:

return leaderBoardUserEntryMap.entrySet().stream()
            .sorted(Map.Entry.comparingByValue(Comparator.comparing(Entry::getScore, Integer::compare).reversed()))
            .limit(5).map(Map.Entry::getValue).collect(Collectors.toList());

Edit: thanks to @Yogesh for the use case

say there are 100 users, and the user that is being searched is at 93. List should return 91, 92, 93, 94, 95. This solution will return 1, 2, 3, 4, 5

Since the use case is to have a subList around the current entry, this could be modified as:

List<GameEntry> selectedEntries =  leaderBoardUserEntryMap.entrySet().stream()
            .sorted(Map.Entry.comparingByValue(Comparator.comparing(GameEntry::getScore, Integer::compare)
                    .reversed())).map(Map.Entry::getValue).collect(Collectors.toList());

int indexOfnewEntry = selectedEntries.indexOf(leaderBoardUserEntryMap.get(uid));
return  selectedEntries.subList(indexOfnewEntry-2,indexOfnewEntry+2);

Edit 2:

The indexOfnewEntry and +- 2 can cause IndexOutOfBoundsException, guarding against it seems a bit tedious, any optimal ways here?

Since the index of the entry might vary on the score, and the subList access further also relies on the number of output desired before/after it. Guarding shall be a better option than any other. Also what could be considered is a customSubList implementation which could internally check your collection type. How to use subList() explains this with top voted answers. I specifically liked this one though :

dataList.subList(Math.max(0, first), Math.min(dataList.size(), last) );

Will using parallelStream() cause problems?

Unless there are any synchronized blocks executed that might alter and make concurrent updates to the stream it wouldn't cause any problems.

But you should know when to use parallel stream - Should I always use a parallel stream when possible?

edited Sep 12 '17 at 14:35

answered Sep 12 '17 at 09:56

Naman

27,789
26
218
353

This will give only top 5 people. What he want is list of 5 users where the current user will be at 3. – Yogesh Badke Sep 12 '17 at 10:09
@YogeshBadke That I believe is already sorted based on the score. isn't it? and then reversed as well for max scores.. – Naman Sep 12 '17 at 10:10
3

What if say there are 100 users, and the user that is being searched is at 93. List should return 91, 92, 93, 94, 95. This solution will return 1, 2, 3, 4, 5. – Yogesh Badke Sep 12 '17 at 10:11
@ YogeshBadke Hmm, seems like I misunderstood the question in that case. @Kaliyug could you confirm this once and add the use case to question as well if it applies. – Naman Sep 12 '17 at 10:14
1

I need exactly what @YogeshBadke has explained :) – Kaliyug Antagonist Sep 12 '17 at 10:16
@KaliyugAntagonist then the edit should help you fetch the sublist you're looking for. – Naman Sep 12 '17 at 10:25
@nullpointer Seems to work but can you check the Edit-1 in my original post ? – Kaliyug Antagonist Sep 12 '17 at 13:45
1

@KaliyugAntagonist Updated the answer. Though the guards is something you can't avoid with your use case being flexible enough to have the `newEntry` at any random index of the list and then trying to access +- values around it. – Naman Sep 12 '17 at 14:36
My bad, I didn't mention this earlier but realized while testing. There seems to be a small problem in the solution, the requirement says 'max two entries that have larger score than the user & two entries with score lesser'. If there are entries with a tie/same score surrounding a particular user, those should be skipped and the next higher/lower entries should be retrieved ... – Kaliyug Antagonist Sep 13 '17 at 07:03
@KaliyugAntagonist Can we have the exact problem statement about selecting the specific users as a new question please? (In favor of not stretching this one.)..Also in general, why should a leaderboard skip equivalent scores?.. And Hints :: (1). you can traverse using the current entry's index and find the start index as soon as the score differ, end index would be +-2 in this case....(2). you can `filter` or find `distinct` for such GameEntries that has same score.(would not be very straightforward though) – Naman Sep 13 '17 at 07:18
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/154297/discussion-between-kaliyug-antagonist-and-nullpointer). – Kaliyug Antagonist Sep 13 '17 at 07:18

Retrieve fixed number of entries around an entry in a map sorted by values

1 Answers1

Linked