Произвеждане на безредици – не толкова тривиално, колкото звучи!
Имате ли доверие в мрежата? (Добре, това е примамка за кликване... но позволете ми да обясня моя опит.) Преди известно време получих странно изискване за промяна в API, който бях разработил. По принцип участващата крайна точка събира и събира информация от услуги и бази данни, за да произведе определен набор от резултати. Искането беше, че наборът от резултати трябва да бъде в произволен ред, което означава, че многократните извиквания към крайната точка ще произвеждат едни и същи данни (ако приемем, че другите услуги и бази данни не се променят), но всеки път в произволна последователност. Освен това, беше желателно всички възможни разбъркани последователности да бъдат еднакво вероятни поради някои нужди, свързани със статистиката. И така, вече знаех как да създам набора от данни, но сега трябваше да мога да го подредя, преди да го изпратя обратно на клиента.
В тази статия ще видим как внедрих моята функция за разбъркване „не-сортиране“ и как я тествах (чрез прилагане на „функции от по-висок порядък“), за да съм достатъчно сигурен, че не съм объркал нещо. И, за да се върна към моя коментар относно доверието в мрежата, ще видим как най-често цитираният (и широко достъпен в мрежата) алгоритъм за разбъркване е напълно погрешен!
Тествам моя алгоритъм за разбъркване
Как можете да тествате алгоритъм за разбъркване? Ако го приложите към даден масив, можете да проверите дали изходният масив има същите стойности като входния масив: това е основно изискване. Но как да тествате дали произвежда множество произволни подреждания и с равни вероятности? (Между другото, това се нарича „равномерно разпределение“, което означава, че всички възможни резултати имат една и съща еднаква вероятност.) Истинският начин за проверка би бил прилагането на „тест за съответствие на хи-квадрат“: по принцип бихте трябва да генерирате много последователности и да направите малко математика, за да видите дали произведеното разпределение е равномерно или не.
Можех да направя това, но избрах по-емпиричен начин на работа. Реших да внедря „функция от по-висок порядък“, която ще приеме функция за разбъркване като вход, ще я извика достатъчен брой пъти, ще запише резултатите и след това ще създам диаграма, за да видя лесно колко еднакви са резултатите. Например извършването на 24 000 стартирания за разбъркване на масив от 4 елемента трябва да произведе нещо като следното.
A-B-C-D: 983 ############################################### A-B-D-C: 1026 ################################################# A-C-B-D: 977 ############################################## A-C-D-B: 993 ############################################### A-D-B-C: 983 ############################################### A-D-C-B: 984 ############################################### B-A-C-D: 1028 ################################################# B-A-D-C: 986 ############################################### B-C-A-D: 1033 ################################################# B-C-D-A: 1016 ################################################ B-D-A-C: 957 ############################################## B-D-C-A: 1022 ################################################# C-A-B-D: 989 ############################################### C-A-D-B: 962 ############################################## C-B-A-D: 993 ############################################### C-B-D-A: 1028 ################################################# C-D-A-B: 955 ############################################# C-D-B-A: 1004 ################################################ D-A-B-C: 1023 ################################################# D-A-C-B: 1051 ################################################## D-B-A-C: 985 ############################################### D-B-C-A: 1020 ################################################# D-C-A-B: 990 ############################################### D-C-B-A: 1012 ################################################ COUNT= 24
Има 24 възможни изхода и ние направихме 24 000 изпълнения, така че всеки изход трябва да е близо до очаквания резултат, 1000. Изглежда, че алгоритъмът, който е произвел този резултат, е добър; всички преброявания са много сходни един с друг. Емпиричната проверка на алгоритмите беше достатъчно добра за моя случай: можех да проверя, че публикуваният алгоритъм е доста лош (както ще видим по-долу) и беше полезно да тествам дали моите реализации не са бъгове.
Следният код реализира идеята, която описахме: той прави определен брой разбърквания, записва колко пъти се е появил всеки изход и създава лентова диаграма с резултатите.
const makeBar = (len, val, max) =>
"#".repeat(Math.round((len * val) / max)); /* 1 */
const testShuffle = (fn, n = 5, times = 4000) => { /* 2 */
const result = {}; /* 3 */
let max = 0; /* 4 */
for (let i = 1; i <= times; i++) { /* 5 */
const arr = Array(n) /* 6 */
.fill(0)
.map((v, i) => String.fromCharCode(65 + i));
const x = fn(arr).join("-"); /* 7 */
result[x] = x in result ? result[x] + 1 : 1; /* 8 */
max = Math.max(max, result[x]); /* 9 */
}
let count = 0; /* 10 */
for (const [key, val] of
Object.entries(result).sort((a,b) => a<b ? -1 : 1)) {
count++; /* 11 */
console.log(`${key}: ${String(val).padStart(5)} ${makeBar(50, val, max)}`);
}
console.log("COUNT=", count); /* 12 */
};
Спомагателна функция makeBar() ще бъде използвана за създаване на хоризонтална лента [1], с която ще създадем нашата диаграма. Функцията testShuffle() получава функция за разбъркване като параметър, размера на масива, който да се използва за тестове (по подразбиране 5) и колко пъти да се направи тестът [2]. Масив ще съхранява резултатите [3]; „карта“ би била алтернатива. Променливата max [4] ще проследи най-големия брой, който намерим. Ще направим цикъл [5], в който ще инициализираме масив с първите букви от азбуката [6], ще го разбъркаме [7] и ще направим низ (като 'B-C-A-D'), за да използвайте като ключ при проследяване на броя [8]. След получаване на всеки нов брой [9] ще видим дали трябва да актуализираме max. След като цикълът приключи, ще преброим колко различни пермутации са произведени [10]. Ще сортираме всички получени последователности по азбучен ред и ще ги преминем в цикъл, актуализирайки броя [11] и отпечатвайки ленти. Накрая ще регистрираме броя [12], което е допълнителна проверка.
Наистина лошото (но популярно?) разбъркване
Добре, сега имаме начин да проверим дали даден масив за разбъркване е добър или не. Нека помислим как да направим самото разбъркване. Наистина лошият алгоритъм, който обикаля, има предимството на самата простота: едноредов! каква е идеята Ключовата концепция трябва да запомни как работи собственият .sort() метод на JavaScript. За да сортирате масив, трябва да предоставите функция, която ще сравни две стойности и ще върне отрицателна стойност, ако първата е по-малка от втората, положителна стойност, ако е по-голяма, и нула, ако стойностите са равни. Алгоритъмът, който можете да намерите на много места, произволно връща отрицателен или положителен резултат (вместо действително да сравнява стойности), така че се очаква, че полученият масив може да е в някакво разстройство. Следва реализация.
const poorShuffle = (arr) => arr.sort(() => Math.random() - 0.5);
Изчисляването на произволно число дава резултат между 0 и 1; изваждането на 0,5 води до резултат между -0,5 и +0,5, така че половината от случаите сравнението ще върви в една посока, а другата половина от случаите ще върви в друга посока. Ако разбърквате масив от два елемента, това наистина ще работи. Но какво се случва с по-големите масиви? За да тествам това, опитах да направя testShuffle(poorShuffle, 3, 10_000), но получих много лоши резултати. Например, правейки 10 000 експеримента с три елемента, резултатите са едностранчиви.
A-B-C: 3777 ################################################## A-C-B: 632 ######## B-A-C: 1258 ################# B-C-A: 643 ######### C-A-B: 605 ######## C-B-A: 3085 ######################################### COUNT= 6
Вместо да получавате шест подобни суми, има много широка вариация. Най-ниският брой е по-малко от една шеста от най-високия брой и това не изглежда наистина случайно. Опитах по-големи масиви и резултатите бяха подобни; например с 4 елемента получих следното.
A-B-C-D: 1886 ################################################## A-B-D-C: 671 ################## A-C-B-D: 165 #### A-C-D-B: 150 #### A-D-B-C: 627 ################# A-D-C-B: 169 #### B-A-C-D: 306 ######## B-A-D-C: 320 ######## B-C-A-D: 162 #### B-C-D-A: 157 #### B-D-A-C: 311 ######## B-D-C-A: 149 #### C-A-B-D: 162 #### C-A-D-B: 132 ### C-B-A-D: 429 ########### C-B-D-A: 452 ############ C-D-A-B: 156 #### C-D-B-A: 474 ############# D-A-B-C: 653 ################# D-A-C-B: 161 #### D-B-A-C: 338 ######### D-B-C-A: 152 #### D-C-A-B: 141 #### D-C-B-A: 1677 ############################################ COUNT= 24
Дори и всичките 24 възможни разбърквания да са произведени, резултатите са още по-непогрешни. Колкото по-дълъг е масивът, толкова по-лоши са резултатите; с пет елемента съотношението между най-ниския и най-високия брой беше около 60! Със сигурност този алгоритъм, въпреки своята простота, не може да се използва. Това беше неочаквано и означаваше, че трябваше да търся по-добър вариант; нека стигнем до това!
Разбъркване чрез сортиране
Първият алгоритъм, който ще опиша, също се основава на идеята за сортиране (като популярната и грешна функция, която отхвърлихме!), но работи на различна основа. Ключовата концепция е проста. За да получите произволна последователност, присвоете произволно число на всеки елемент от масива, сортирайте масива по това число и ще създадете напълно произволно подреждане. Това може да се реализира като едноредов - но, добре, не твърде кратък...
const sortingShuffle = (arr) =>
arr
.map((v) => ({ val: v, key: Math.random() })) /* 1 */
.sort((a, b) => a.key - b.key) /* 2 */
.map((o) => o.val); /* 3 */
Нека да видим как работи това. Първо [1] вземаме масива за разбъркване и произвеждаме нов масив от обекти с оригиналната стойност на val и произволно число на key. След това [2] сортираме масива чрез сравняване на ключовите стойности. Накрая [3] отменяме картографирането, като просто извличаме стойностите val. Имаме произволно разбъркан масив, практически без код! Направих няколко теста и получих добри резултати като следните, в които разбърках масив от три елемента 60 хиляди пъти! (Отне около една десета от секундата на моята машина.) Тествах и по-дълги масиви - но винаги получавах добри резултати, така че имах причини да вярвам, че внедряването ми е правилно.
A-B-C: 10003 ################################################# A-C-B: 9983 ################################################# B-A-C: 9915 ################################################# B-C-A: 10001 ################################################# C-A-B: 9976 ################################################# C-B-A: 10122 ################################################## COUNT= 6
Този метод е доста ефективен и за малки масиви вероятно е най-добрият. За по-големи масиви сортирането може да отнеме малко повече време и някои основни резултати от компютърните науки казват, че това поведение ще се влоши. (Например, ако удвоите размера на масива, времето ще се удвои повече от два пъти.) Проверих литературата и намерих по-добър алгоритъм, чиято производителност е пропорционална на размера на масива, както бихте желали. Любопитно е, че начинът, по който работи алгоритъмът, по някакъв начин е свързан с Bogosort, известен също като „най-лошият алгоритъм за сортиране досега“! Нека първо разгледаме този грандиозно лош алгоритъм за сортиране и след това да го превърнем в един добър за разбъркване.
Повторение на сесия с отворен код
Отстраняването на грешки в производствено уеб приложение може да бъде предизвикателство и отнема много време. OpenReplay е алтернатива с отворен код на FullStory, LogRocket и Hotjar. Позволява ви да наблюдавате и възпроизвеждате всичко, което вашите потребители правят, и показва как се държи приложението ви при всеки проблем. Това е като да отворите инспектора на браузъра си, докато гледате през рамото на потребителя си. OpenReplay е единствената налична в момента алтернатива с отворен код.
Приятно отстраняване на грешки, за модерните екипи за интерфейс — Започнете да наблюдавате вашето уеб приложение безплатно.
Сортиране случайно
Ако изучавате компютърни науки, ще бъдете научени на няколко метода за сортиране - и всеки се опитва да бъде по-добър от останалите и да работи с максимална скорост. Съществува обаче един метод, който е напълно неефективен. За да го опишем, нека си представим как можете да разбъркате тесте карти. Bogosort го прави много просто:
- хвърлете тестето във въздуха и оставете всички карти да паднат на пода.
- вземете картите в произволен ред, толкова произволно, колкото желаете
- проверете дали (по чиста случайност!) картите са наред.
- Ако е така, сте готови!
- Но ако не (най-вероятно…) върнете се към стъпка 1 и опитайте отново!
Това е наистина лошо - и се надявам, че няма да се изкушите да го изпробвате! Въпреки това идеята за избиране на елементи в произволен ред води до интересен начин за извършване на разбъркване и това е, което ще опишем.
Методът на разместване на Фишър-Йейтс
Методът на Фишър-Йейтс е перфектен начин за разбъркване на тесте карти. Как работи? По принцип изберете цялата колода. Докато в него има останали карти, произволно изберете всяка карта, приберете я и повторете. Когато тестето е изчерпано, ще трябва да приберете картите по напълно случаен начин. Докато разбъркваме масив, можем да се справим по-добре, като дори не изискваме втори масив. За да разбъркаме масив от N елемента, можем просто да направим:
for I starting at N-1, going down to 1: let J be a random number between 0 and I inclusive exchange the elements at positions I and J
Нуждаем се от функция, която при дадено число K ще генерира число между 0 и самото K. Можем да управляваме това, като използваме Math.random() и Math.floor() както следва.
const randomInt = (k) => Math.floor((k + 1) * Math.random());
Защо това работи? Първо, запомнете, че Math.random() произвежда число, по-голямо или равно на нула, но по-малко от 1. Ако умножите това по (K+1), резултатът е по-голям или равен на нула, но по-малък от (K+1). Ако вземете цялата част от него с Math.floor(), оставате с цяло число, по-голямо или равно на нула и по-малко от (K+1) - тоест по-малко или равно на K, както желаете. Може също да се покаже, че всички резултати са еднакво вероятни. С тази функция можем да завършим нашия код за разбъркване.
const fisherYatesShuffle = (arr) => {
for (let i = arr.length - 1; i > 0; i--) {
const j = randomInt(i);
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
};
Функцията работи, както е описано по-горе, и произвежда равномерни произволни разбърквания. Примерно изпълнение с нашата функция за тестване от предишната статия показва доброто му поведение.
A-B-C-D: 1028 ################################################ A-B-D-C: 1005 ############################################### A-C-B-D: 946 ############################################ A-C-D-B: 1017 ################################################ A-D-B-C: 988 ############################################## A-D-C-B: 1049 ################################################# B-A-C-D: 1013 ################################################ B-A-D-C: 952 ############################################# B-C-A-D: 1043 ################################################# B-C-D-A: 935 ############################################ B-D-A-C: 1066 ################################################## B-D-C-A: 1041 ################################################# C-A-B-D: 940 ############################################ C-A-D-B: 1007 ############################################### C-B-A-D: 982 ############################################## C-B-D-A: 1029 ################################################ C-D-A-B: 994 ############################################### C-D-B-A: 992 ############################################### D-A-B-C: 972 ############################################## D-A-C-B: 1004 ############################################### D-B-A-C: 995 ############################################### D-B-C-A: 971 ############################################## D-C-A-B: 986 ############################################## D-C-B-A: 1045 ################################################# COUNT= 24
Ние сме готови! Ако трябва да обработвате по-големи масиви и базираният на сортиране алгоритъм за разбъркване отнема твърде много време, алгоритъмът на Fisher-Yates ще се справи по-добре.
Резюме
В тази статия видяхме специално изискване, което получих, което предполага сортиране на изхода от извикване на услуга по произволен начин и обсъдихме как да тестваме всеки възможен алгоритъм и завършихме с прилагане на нашия анализ към много често споменавано разбъркване алгоритъм — който се оказа доста лош!
Разгледахме и двойка алгоритми за разбъркване:
- Първият имаше плюса, че беше много прост и кратък, но не можеше да се държи толкова добре за дълги масиви.
- Вторият алгоритъм беше малко по-сложен, но работата му беше гарантирано добра.
Въпреки че има повече алгоритми за разбъркване на данни, те бяха достатъчни за моите изисквания (започнах с помощта на алгоритъма за разбъркване на сортиране, но след това го промених на Fisher-Yates, за да съм в безопасност, в случай че резултатът от API стане много голям). Кодирането от страна на сървъра обикновено не ви кара да се занимавате с този вид проблем, така че изискването, което моите потребители ми дадоха, беше доста интересно.
И също така предостави напомняне да не се доверявате сляпо на код, който можете да изтеглите от мрежата — „получавате това, за което плащате“ също се отнася за кода!
Първоначално публикувано в https://blog.openreplay.com на 9 март 2022 г.
