Diskuze: Porovnání každého záznamu s každým

Aktivity

Vakos

Tvůrce

Vakos:7.7.2019 0:00

Ahoj, chtěl bych udělat program, kde z porovnaných dat by vytvořil seřazený seznam.

Dejme tomu, že mám seznam předmětů, kde chci porovnat jejich velikost a udělat index od největšího po nejmenší.

Problém je, že nechci nikde zapisovat jejich velikost v číselné podobě, ale chci je první všechny manuálně porovnat a na základě mého porovnání udělat index. (Důvod toho způsobu je ten, že toto je jen příklad a v konkrétním případě, který nechci zmiňovat, se jedná o abstraktní data a lze je porovnat pouze takto, subjektivně)

Jak by se tohoto dalo dosáhnout? Nějaké tipy na články které by mi mohly pomoct?

Díky

Editováno 7.7.2019 0:00

Odpovědět

7.7.2019 0:00

"Jediný způsob, jak dělat skvělou práci, je milovat to, co děláte. Pokud jste to ještě nenašli, hledejte dál. Ne...

Neaktivní uživatel

Tvůrce

Neaktivní uživatel:7.7.2019 1:19

Při použití standardních řadících algoritmů není potřeba nikam zapisovat jednotlivé "velikosti" - prostě porovnáváš jeden prvek s jiným.

[Termín k vyhledání Total Order]

Předpokládám teď, že to tvoje porovnávání je tranzitivní, antisymetrické a reflexivní. To jsou totiž přesně 3 požadavky na komparátor použitý v řadícím algoritmu, pokud chci docílit totálního seřazení.

O co teda jde lidsky řečeno:

Tranzitivita: Pokud platí, že A ® B a také B ® C => A ® C.
Pokud je Adam menší než Bob a Cyril je větší než Bob, pak je Cyril větší než Adam.

Antisymetrie: A ® B a B ® A pak určitě A = B nebo jinak řečeno A ® B => NOT B ® A pro všechna A různá od B.
Pokud je Adam alespoň tak vysoký jako Bob a Bob je alespoň tak vysoký jako Adam, pak jsou stejně velcí. Jinak řečeno, pokud nejsou stejně velcí, pak nemůžou být oba alespoň stejně velcí jako ten druhý.

Reflexivity: A ® A pro všechna A.
Adam je alespoň tak velký jako Adam.

Všimni si, že na relační symbol ® dobře sedí neostrá nerovnost. Menší rovno nebo věští rovno.

Pokud tohle platí ve tvém systému, tak bys to měl normálně seřadit quicksortem nebo mergesortem správně.

Zdroje:
https://en.m.wikipedia.org/…/Total_order
https://en.m.wikipedia.org/…ng_algorithm

Nahoru Odpovědět

7.7.2019 1:19

Neaktivní uživatelský účet

Peter Mlich

Člen

Peter Mlich:7.7.2019 22:13

https://www.itnetwork.cz/…itmy-razeni/

Pokud mas male pole, tak je vyhodny insert sort, ale misto od zacatku porovnavas vzdy stred pole, stred zbyle casti, atd.
Pokud mas delsi, tak je lepsi quick sort.

A co ti brani pouzit nativni algoritmus tveho programovaciho jazyka? Ze potrebujes vytvaret vlastni reseni?
https://www.geeksforgeeks.org/…n-list-sort/

Editováno 7.7.2019 22:15

Nahoru Odpovědět

7.7.2019 22:13

Peter Mlich

Člen

Peter Mlich:8.7.2019 8:52

https://mlich.zam.slu.cz/…sorting3.htm
Jeste muzes zkusit takovy muj pokus. Ale neni to moc dodelane a prehledne
2. Vyberes Efectivity test, kliknes Start efectivity.

Test postupne zvysuje velikost pole a zkousi algoritmus, meri cas. Pokud soucet presahne nejakou hodnotu, dalsi pokusy zastavi. Cili, cim vic cisel, tim rychlejsi algoritmus.

1. U Algorirmus kliknes (fast), to by melo zaskrtnout 15 algoritmu. Pocet prvku je vybrany 1000. Kliknes Start.

Tento test vytvori statistiky algoritmu, cas, pocet nutnych porovnavani a tak.
Pak si tam dej treba all (37 algoritmu)

Nevyhoda je, ze tam muzou byt chyby a neco je nedodelane a je tam chaos v kodu, obcas.

Nej algoritmy jsou zname:

cas: tim sort (insert kombinovany s list-merge), quick sort, list merge (upraveny merge sort)
cas pro specialni pripad: counting, radix sort
pocet porovnani: tim sort, insert to middle, list merge
male naroky na pamet: tim sort, quick sort

Pro 10.000 prvku:

sortTimsort - 120432
XsortInsertMiddle_1a - 123217 cmp operaci porovnani 2 cisel a<=b (tam mam asi chybku, obvykle byva lepsi nez tim)
sortListMerge_2a - 123653 (presunuje z pole a do b a zpet, takze potrebuje extra pamet)
sortQuick2_2a - 165071 (v nejhorsi variante je ale pocet operaci stejny jako bubble sort)

A zajimave mozna bude pro tebe porovnani 4 cisel, pokud chces stahnout pocet cmp a budes si pamatovat vysledky prechozich operaci. Viz Taskkill, ti to krasne vedecky rozepsal
https://mlich.zam.slu.cz/…-sort-x2.htm
Pokud bys mel moznost multi-threading, tak lze udelat algoritmus, ktery otevre 3 vlakna. A jedno z nich po 3 krocich serazeni ukonci. Cili, idealni algoritmus. cmp = n - 1, pocet porovnani je roven (poctu prvku - 1). U 10.000 by to bylo 9.999 a ne 120.000 Ale mel bys rozjetych 10.000 vlaken, nebo, tak nejak (mozna 10.000x10.1000). V podstate neco jako bubble sort.

Editováno 8.7.2019 8:52

Nahoru Odpovědět

8.7.2019 8:52

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 4 zpráv z 4.