You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Alex D Herbert (Jira)" <ji...@apache.org> on 2019/09/10 19:34:00 UTC
[jira] [Resolved] (RNG-114) Improve ListSampler shuffle algorithm to detect instances of RandomAccess
[ https://issues.apache.org/jira/browse/RNG-114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alex D Herbert resolved RNG-114.
--------------------------------
Fix Version/s: 1.3
Resolution: Implemented
In master.
> Improve ListSampler shuffle algorithm to detect instances of RandomAccess
> -------------------------------------------------------------------------
>
> Key: RNG-114
> URL: https://issues.apache.org/jira/browse/RNG-114
> Project: Commons RNG
> Issue Type: Improvement
> Components: sampling
> Affects Versions: 1.2
> Reporter: Alex D Herbert
> Assignee: Alex D Herbert
> Priority: Minor
> Fix For: 1.3
>
> Attachments: LinkedListShufflePerformance.png
>
> Time Spent: 40m
> Remaining Estimate: 0h
>
> The ListSampler shuffle algorithm uses the input list {{set(index)}} method. If this runs in constant time then the algorithm is fast. If the list is not an instance of {{java.util.RandomAccess}} such as a LinkedList the algorithm will suffer from performance slowdown for large lists.
> This is handled in the JDK Collections.shuffle method by detecting if the list is not an instance of RandomAccess. If so the list {{set(index)}} method is avoided and the list is traversed for update using its iterator.
> Tasks:
> * Benchmark the ListSampler method verses Collections.shuffle with ArrayList and LinkedList
> * Update the ListSampler to have comparable performance to Collections.shuffle
--
This message was sent by Atlassian Jira
(v8.3.2#803003)