Aloin selaamaan mielenkiinnosta Java 8:n apista java.util -paketin Arrays -tietotyypin Javan tarjoamia lajittelumetodeita ja niiden sanallisia selityskuvauksia.
olioita sisältävä taulukko, mikä primitiivitietotyyppi int[]-taulukkokin on, mitä Java käsittelee primaaritietotyyppialkioita sisältävät taulukotkin olioina, on mahdollista lajitella.
Ainakin Quick sort on Javassa implementoitu, mutta miten tehokas tuo Object[] -eli omia tietotyyppejä sisältävä taulukon lajittelu on, millä argumentein tai parametrein se tuo Arrays.sort(Object[] obj) -stattinen metodi lajittelee taulukon.
Tuossa Java Api - kuvauksessa todetaan, että lomituslajittelun ei tarvitse olla vakaa, ja tuo ei ainakaan tuo mainitsemani metodi käytä varmaankaan lomituslajittelua, vaikka se on monessa käytännon sovellustilanteessa hyvinkin käyttokelpoinen ja nopea. Tuolla puhutaan jotain, että se perustuu peter McIlroyn tekniikkaan, mikä on perua vuodelta 1993 suora lainaus:
The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techniques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.
Lähde https://docs.oracle.com/javase/8/docs/api/java/
Varmaan tilanteita ohjelmoijalla edessä jossain sovellustapauksissa, että tuo Javan valmiiksi tarjoamat lajittelut ei käy, ja lomittelulajittelulle olisi kysyntää, vai olenko väärässä.
Silloin kun natiivikirjaston menetelmät eivät sovellu omaan käyttöön, puhutaan jo hyvin matalan tason jutuista, joissa ei riitä simppeli takuu O(n log n):stä vaan mitataan oikeasti niitä viimeisiäkin millisekunteja tai jotain RAM-muistin "usage patterneja".
Antamasi linkin takana lukee aivan päinvastoin, eli lajittelu on stabiili: "For example, the algorithm used by sort(Object[]) does not have to be a MergeSort, but it does have to be stable."
TimSort on lomituslajittelun (merge sort) sovellus ja siis yleensä sitä nopeampi. Vertailut perustuvat compareTo-metodiin.
Ei ole juurikaan tilannetta, jossa ohjelmoijan kannalta olisi tarve juuri tietylle lajittelualgoritmille, vaan tarve on tietyille ominaisuuksille kuten nopeudelle tai muistinkäytölle. Toisaalta kun on tunnettuja algoritmeja, on helpompi ilmaista vaatimukset sen kautta, mikä tunnettu algoritmi riittää. Esimerkiksi juuri lajitteluun on lukuisia vaihtoehtoja, joiden käytännön erot ovat pienet.
Joo, epäilinkin, että varmaan aika vähissä tulee ainakaan oman elämäni aikana,jos päädyn johonkin ohjelmistofirmaan tekemään jotain koodin ylläpitotehtäviä, niin ei tarvitse alkaa ihan juuritasolta ohjelmoimaan.
Jere Sumell kirjoitti:
int[]
Et kysynyt tästä, mutta Arrays.sort(int[])-funktiota ei tosiaan kannata käyttää. Sen aikavaativuus patologisilla taulukoilla on O(n^2).
Tämä on helppo missata dokumentaatiosta, jossa sanotaan koomisesti "This algorithm offers O(n log(n)) performance on many data sets".
Esimerkki nopeasta int-taulukon järjestelystä: https://lemire.me/blog/2021/04/09/how-fast-can-you-sort-arrays-of-integers-in-java/
jlaire kirjoitti:
Et kysynyt tästä, mutta Arrays.sort(int[])-funktiota ei tosiaan kannata käyttää. Sen aikavaativuus patologisilla taulukoilla on O(n^2).
Hienoa, kun otit asian esille. pitää tosiaan vältellä expontetiaalisen suoritusajan tarjoavia ratkaisuja, vaikka pienellä syotekoolla melkein sama mitä käyttää käytännossa, mutta syotekoon kasvaessa tulee äitiä ikävä, jos ratkeavuus on expotentiaalisessa ajassa, vaikka algoritmi olisikin algoritmisesti ratkaistavissa, ja suoritus päättyisi joskus.
Jere Sumell kirjoitti:
pitää tosiaan vältellä expontetiaalisen suoritusajan tarjoavia ratkaisuja,
Muistetaanpa silti, että eksponentiaalinen olisi 2^n ja tulee kohtuuttomaksi jo kymmenien kokoisella syötteellä, kun taas edellä mainittu n^2 on ihan vain polynomi ja merkittävästi pienempi ja sopii yleensä vielä tuhansiin asti syötekoossa.
The Alchemist kirjoitti:
Silloin kun natiivikirjaston menetelmät eivät sovellu omaan käyttöön, puhutaan jo hyvin matalan tason jutuista, joissa ei riitä simppeli takuu O(n log n):stä vaan mitataan oikeasti niitä viimeisiäkin millisekunteja tai jotain RAM-muistin "usage patterneja".
lollotilollotilolloo.
Jaa että javaa kirjotellessa aletaan (tahi edes kannattaa) harrastaa mikro-optimointia?
Tämä on klassinen esimerkki itseristiriidasta (ks. "oxymoron" på lontoo).
Aihe on jo aika vanha, joten et voi enää vastata siihen.