Geek tričko zdarma Geek tričko zdarma
Tričko zdarma! Stačí před dobitím bodů použít kód TRIKO15. Více informací zde

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

Aktivity (2)
Avatar
Vakos
Redaktor
Avatar
Vakos:7. července 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. července 0:00
Odpovědět 7. července 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...
Avatar
Taskkill
Redaktor
Avatar
Odpovídá na Vakos
Taskkill:7. července 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  +3 7. července 1:19
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:7. července 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. července 22:15
 
Nahoru Odpovědět 7. července 22:13
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:8. července 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
  • XsortInsertMid­dle_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. července 8:52
 
Nahoru Odpovědět 8. července 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.