Как эффективно случайным образом выбирать элемент массива без повторов?
Я знаю, что этот вопрос существует во многих обличьях, но я не смог найти ответ, связанный с моей конкретной проблемой эффективности.
У меня есть код ниже, который работает отлично.
У меня есть массив из 10 элементов, из которого я случайно выбираю элемент (при нажатии клавиши ввода). Код хранит массив из 5 самых последних вариантов, которые нельзя выбрать случайным образом (чтобы избежать слишком много повторений с течением времени).
- Как установить атрибут id элемента HTML динамически с помощью angularjs (1.x)?
- В чем разница между «throw new Error» и «throw someObject»?
- Как получить данные POST с urlencoded с помощью $ http без jQuery?
- Выберите все содержимое текстового поля, когда он получает фокус (Vanilla JS или jQuery)
- Typcript - расширение classа ошибок
Если функция selectName () изначально выбирает имя, которое использовалось в последних 5, оно просто ломается и снова вызывает себя, повторяя, пока не найдет «уникальное» имя.
У меня есть два вопроса:
-
Правильно ли говорить, что это «рекурсивная функция»?
-
Я обеспокоен тем, что теоретически это может продолжаться в течение длительного времени, прежде чем найти уникальное имя – есть ли более эффективный способ сделать это?
Спасибо за любую помощь.
var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"]; var b = []; var chooseName = function () { var unique = true; b.length = 5; num = Math.floor(Math.random() * a.length); name = a[num]; for (i = 0; i < a.length; i++) { if (b[i] == name) { chooseName(); unique = false; break; } } if (unique == true) { alert(name); b.unshift(name); } } window.addEventListener("keypress", function (e) { var keycode = e.keyCode; if (keycode == 13) { chooseName(); } }, false); - Как очистить все параметры в раскрывающемся списке?
- Может ли (a == 1 && a == 2 && a == 3) когда-либо оценивать значение true?
- Использование Chrome, как найти, какие события связаны с элементом
- AngularJS: ng-selected не отображает выбранное значение
- Как включить этот обратный вызов в promise, используя async / wait?
- Если JavaScript имеет первоclassные функции, почему не вызывает эту функцию в переменной?
- Как трубы и монады работают вместе в JavaScript?
- Контекст функции JavaScript Неправильный
Всякий раз, когда элемент выбран, переместите его в обратную сторону массива и произвольно выберите из среза исходного массива array.slice(0, -5) .
var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"]; var chooseName = function () { var unique = true; num = Math.floor(Math.random() * a.length - 5); name = a.splice(num,1); a.push(name); } window.addEventListener("keypress", function (e) { var keycode = e.keyCode; if (keycode == 13) { chooseName(); } }, false);
EDIT: Это также имеет побочный эффект от того, что какие-либо переменные не совпадают с списком несправедливого недостатка, которого они не будут рассматривать в первых N вызовах. Если это проблема для вас, возможно, попробуйте сохранить статическую переменную где-нибудь, чтобы отслеживать размер используемого fragmentа и максимально использовать его в B (в данном случае 5). например
var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"]; B = 5; //max size of 'cache' N = 0; var chooseName = function () { var unique = true; num = Math.floor(Math.random() * a.length - N); N = Math.min(N + 1, B); name = a.splice(num,1); a.push(name); }
Мне нравится комментатор @ Идея Юрия Галантера о выборе элементов случайным образом, пока все не будут приняты, и только тогда повторяется, так что вот реализация:
function randomNoRepeats(array) { var copy = array.slice(0); return function() { if (copy.length < 1) { copy = array.slice(0); } var index = Math.floor(Math.random() * copy.length); var item = copy[index]; copy.splice(index, 1); return item; }; } var chooser = randomNoRepeats(['Foo', 'Bar', 'Gah']); chooser(); // => "Bar" chooser(); // => "Foo" chooser(); // => "Gah" chooser(); // => "Foo" -- only repeats once all items are exhausted.
Я рекомендую вам использовать underscore.js , это будет очень просто.
Функция shuffle реализуется равномерно распределенным образом, поэтому вероятность повторения будет низкой, если массив a содержит больше данных.
var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"]; b = _.shuffle(a).slice(0,5); console.log(b);
Когда вы создаете экземпляр Shuffler, дайте ему массив в качестве параметра. Он создаст копию массива, и каждый раз, когда будет вызываться next (), он вернет случайный элемент из копии и удалит его из массива копий, чтобы повторы не были возможны.
var Shuffler = function(a) { var aCopy = [], n = 0; // Clone array for (n=0; n
Да, это рекурсивно, и поскольку оно не уменьшает состояние, оно теоретически может продолжаться вечно.
Я предполагаю, что изменение массива недопустимо, так как в противном случае вы могли бы просто удалить недавние варианты из массива и оттолкнуть их обратно в качестве недавнего переполнения буфера выбора.
Вместо этого: исключайте элементы буферизации в конце массива из выделения. (Buffersize начинается с 0 и увеличивается до вашего предустановленного буферизамакса, когда в буфер добавляются последние варианты.) Когда вы делаете выбор, вы сравниваете его с вашими избранными вариантами bufffersize. Если вы найдете совпадение, вы выбираете вместо этого исключенный элемент.
Очевидно, что до сих пор неэффективна необходимость проверять каждый недавний выбор в буфере, чтобы избежать совпадения. Но у него есть эффективность, позволяющая избежать возможной рекурсии.
Эта работа как прелесть для меня без повторения.
var Random_Value = Pick_Random_Value(Array);
function Pick_Random_Value(IN_Array) { if(IN_Array != undefined && IN_Array.length > 0) { var Copy_IN_Array = JSON.parse(JSON.stringify(IN_Array)); if((typeof window.Last_Pick_Random_Index !== 'undefined') && (window.Last_Pick_Random_Index !== false)) { if(Copy_IN_Array[Last_Pick_Random_Index] != undefined) { Copy_IN_Array.splice(Last_Pick_Random_Index,1); } } var Return_Value = false; if(Copy_IN_Array.length > 0) { var Random_Key = Math.floor(Math.random() * Copy_IN_Array.length); Return_Value = Copy_IN_Array[Random_Key]; } else { Return_Value = IN_Array[Last_Pick_Random_Index]; } window.Last_Pick_Random_Index = IN_Array.indexOf(Return_Value); if(window.Last_Pick_Random_Index === -1) { for (var i = 0; i < IN_Array.length; i++) { if (JSON.stringify(IN_Array[i]) === JSON.stringify(Return_Value)) { window.Last_Pick_Random_Index = i; break; } } } return Return_Value; } else { return false; } }