[jira] [Updated] (RNG-114) Improve ListSampler shuffle algorithm to detect instances of RandomAccess

["Alex D Herbert (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/RNG-114?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Alex D Herbert updated RNG-114:
-------------------------------
    Attachment: LinkedListShufflePerformance.png

> 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
>         Attachments: LinkedListShufflePerformance.png
>
>
> 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)