Keskustelu: Koodit: Java: Lukujen määrä

Ohjelma laskee lukujen määrän taulukosta. Esimerkiksi, jos luvut ovat 2,5,5,7 luvun 2 määrä on 1 ja 5 määrä on 2. Taulukko lajitellaan ensin (tässä esimerkikssä vaihtolajittelulla), jotta sitä olisi helpompi käsitellä.

Koodi

import java.util.Scanner;
public class Lukujen_maara {
 public static void main(String[] args){
  Scanner syote = new Scanner(System.in);
  int maara = 0;
  //Syötetään lähtötiedot.
  System.out.println("Syötä lukujen määrä.");
  maara = syote.nextInt();
  int[] luvut = new int[maara];
  //Syötetään luvut.
  for (int x = 0; x < maara; x++){
   luvut[x] = syote.nextInt();
  }

  //Järjestetään taulukko vaihtolajittelulla (myös muu lajittelu käy), jotta sitä on helpompi käsitellä.
  int temp = 0;
  for (int x = 0; x < luvut.length-1; x++){
   for (int y = x+1; y < luvut.length; y++){
    if (luvut[x] > luvut[y]){
      temp = luvut[x];
      luvut[x] = luvut[y];
      luvut[y] = temp;
    }
   }
  }

  //Otetaan taulukosta minimi -ja maksimiarvo
  //ja katsotaan lukujen määrä tällä välillä.
  //Koska taulukko on lajiteltu, pienin arvo löytyy ensimmäisestä alkiosta
  //ja suurin arvo viimeisestä alkiosta.
  int min = luvut[0];
  int max = luvut[maara-1];
  int luvunMaara = 0;

  //Lasketaan lukujen määrä lukuväliltä käytämme tähän muuttaa x.
  //luvunMaara muuttuja kertoo luvun x määrän.
  //Lopuksi näytetään kyseisen luvun määrä
  //Jos lukuja ei ole yhtään kappaletta luvun määrä ei näytetä
  for (int x = min; x <= max; x++){
   luvunMaara = 0;
   //Lasketaan luvun x määrä.
   for (int y = 0; y < maara; y++){
    if (x == luvut[y]){
      luvunMaara++;
    }
   }
   //Näytetään tulos.
   if (luvunMaara > 0){
    System.out.println(x + ":" + luvunMaara);
   }
  }
 }
}

Itse tekisin yksinkertaisesti käyttämällä map tietorakennetta, Javalla vissiin HashMap. Samalla tyylillä pystyy myös esimerkiksi yksinkertaisesti laskemaan sanojen määrät tiedostossa.

Esimerkiksi 8th ohjelmointikielelellä ohjelma yksinkertaistuisi:

m:new constant numbermap

: process-numbers  \ number --
  numbermap over m:@ null? if  \ Onko avain olemassa?
    drop swap 1 m:! drop       \ Ei, lisätään se ja tallennetaan 1.
  else
    n:1+ rot m:_! drop         \ Löytyy, lisätään yksi laskuriin.
  then ;

: print-sorted-number-count
  numbermap m:keys ' s:cmp a:sort ( dup . ":" . space m:@ . cr ) a:each! 2drop ;

: app:main
  [1,2,3,1,5,9,5,3,1,2,9,7,6,3] ' process-numbers a:each! drop
  print-sorted-number-count
  bye ;

Ohjelman tulos on:

1: 3
2: 2
3: 3
5: 2
6: 1
7: 1
9: 2

Ja jos haluttaisiin näyttää tulokset vain tietyltä väliltä, voitaisiin map:in avaimet filteröidä vain tietylle välille.

Itse tekisin C#:lla tähän tyyliin. Etuna että koodista näkee melko suoraan ilman kommenttejakin mitä ollaan tekemässä.

foreach (var grp in luvut.GroupBy(l=>l)) {
    Console.WriteLine($"{grp.Key}: {grp.Count()}");
}

Tällä katsotaan, onko luku uniikki

for (int x = min; x <= max; x++){
   luvunMaara = 0;
   //Lasketaan luvun x määrä.
   for (int y = 0; y < maara; y++){
    if (x == luvut[y]){
      luvunMaara++;
    }
   }
   //Näytetään tulos.
   if (luvunMaara == 1){
    System.out.println(x + ":uniikki");
   }
 }

Näistä viesteistä on nyt nähtävissä ainakin se, että Javalla ja 8th:llä tulee todella sotkuisia ratkaisuja ongelmiin, jotka muilla kielillä voidaan ratkoa muutamalla rivillä melkoisen itsedokumentoivaa koodia.

Tronic kirjoitti:

... 8th:llä tulee todella sotkuisia ratkaisuja ongelmiin, jotka muilla kielillä voidaan ratkoa muutamalla rivillä melkoisen itsedokumentoivaa koodia.

Tuossa ratkaisussani on vain muutama rivi koodia. Mikä tekee ratkaisusta, mistä näkee yhdellä silmäyksellä mitä se tekee sotkuisen? Python toteutus ei ole tuota paljon lyhyempi.

Grez:in postaama C# toteutus on lyhyt ja luettava, mutta en tietäisi minkä mukaan LINQ metodi GroupBy(l=>l) toimii lukematta dokumentaatiota.

jalski kirjoitti:

Grez:in postaama C# toteutus on lyhyt ja luettava, mutta en tietäisi minkä mukaan LINQ metodi GroupBy(l=>l) toimii lukematta dokumentaatiota.

Johtunee siitä, että et säännöllisesti koodaa C#:lla.

Ei taida olla yhtään vähänkään monipuolisempaa kieltä, jonka kaikki jutut olisi täysin dokumentaatiota lukematta itsestäänselviä.

Tronic kirjoitti:

... 8th:llä tulee todella sotkuisia ratkaisuja ongelmiin, jotka muilla kielillä voidaan ratkoa muutamalla rivillä melkoisen itsedokumentoivaa koodia.

Alla hiukan lyhyemmin:

: app:main
  [ 1, 2, 3, 1, 3, 2, 5, 7, 9 ] ' >s a:group
  m:keys ' s:cmp a:sort ( swap over m:@ a:len nip rot "%s: %d\n" s:strfmt . ) a:each! 2drop
  bye ;

jalski kirjoitti:

Grez:in postaama C# toteutus on lyhyt ja luettava, mutta en tietäisi minkä mukaan LINQ metodi GroupBy(l=>l) toimii lukematta dokumentaatiota.

Onhan tuo nyt ihan selvä, että metodi palauttaa avaimen, jonka mukaan käsittelyssä oleva rivi ryhmitellään. Tuollaisen funktion joutuisi varmaan jossain vaiheessa kirjoittamaan itse, jos käytetty kieli ei tarjoa valmista implementaatiota.

(Jos olet aina kirjoittanut ryhmittelyä vaativissa tilanteissa käsin for-silmukan ja rakentanut ryhmittelyn usealla rivillä itseään toistavaa koodia, niin olet tehnyt väärin.)

The Alchemist kirjoitti:

(11.11.2019 05:04:35): ”– –” Onhan tuo nyt ihan selvä, että metodi palauttaa...

Olet sinä epeli! Tehtävässähän ei oikeasti vaadita ryhmittelyä vaan pitää laskea taulukossa olevien lukujen määrät. Kumman muuten luulet olevan tehokkaampi muistinkäytön ja nopeuden kannalta laskettaessa esimerkiksi raamatussa olevien sanojen määrää: tallentaa sanojen lukumäärät map:iin ja tulostaa ne vai tallentaa map:iin lista samoista luvuista ja tulostaa lopuksi listan pituus?

jalski kirjoitti:

Kumman muuten luulet olevan tehokkaampi muistinkäytön ja nopeuden kannalta laskettaessa esimerkiksi raamatussa olevien sanojen määrää: tallentaa sanojen lukumäärät map:iin ja tulostaa ne vai tallentaa map:iin lista samoista luvuista ja tulostaa lopuksi listan pituus?

Sitä kannattaa alkaa miettiä sitten kun sillä nopeudella on jotain merkitystä. Jos haluat laskea raamatun sanojen määrän, niin minusta on järkevämpää käyttää koodin kirjoittamiseen aikaa 40 sekuntia ja tietokone laskee sitä määrää 0,01 sekuntia, kuin optimoida suoritusnopeutta ja joutua kirjoittamaan koodia 50 sekuntia, jolloin tietokone laskeekin sitä määrää vain 0,001 sekuntia. Huomautan vielä että ihmistyön aika maksaa (suomessa) kymmeniä euroja tunnilta, kun taas koneaika maksaa alle sentin tunnilta.

Toinen merkittävä tekijä on tietysti sitten luettavuus. Eli jos jonkin optimoidun koodin ylläpitoon kuluu taas sitä ihmisaikaa minuutin enemmän niin optimointiedun pitäisi olla luokkaa kymmeniä tunteja CPU-aikaa.

Tilannehan voisi olla joku aivan muu jos oltaisiin tekemässä jotain muuta kuin raamatun sanojen laskemista. Eli jotain sellaista, jota vaikka tuhannet tietokoneet laskisi viikkokaupalla CPU:t punaisina.

Grez kirjoitti:

Sitä kannattaa alkaa miettiä sitten kun sillä nopeudella on jotain merkitystä. Jos haluat laskea raamatun sanojen määrän, niin minusta on järkevämpää käyttää koodin kirjoittamiseen aikaa 40 sekuntia ja tietokone laskee sitä määrää 0,01 sekuntia, kuin optimoida suoritusnopeutta ja joutua kirjoittamaan koodia 50 sekuntia, jolloin tietokone laskeekin sitä määrää vain 0,001 sekuntia. Huomautan vielä että ihmistyön aika maksaa (suomessa) kymmeniä euroja tunnilta, kun taas koneaika maksaa alle sentin tunnilta.

Toinen merkittävä tekijä on tietysti sitten luettavuus. Eli jos jonkin optimoidun koodin ylläpitoon kuluu taas sitä ihmisaikaa minuutin enemmän niin optimointiedun pitäisi olla luokkaa kymmeniä tunteja CPU-aikaa.

Tilannehan voisi olla joku aivan muu jos oltaisiin tekemässä jotain muuta kuin raamatun sanojen laskemista. Eli jotain sellaista, jota vaikka tuhannet tietokoneet laskisi viikkokaupalla CPU:t punaisina.

Olet oikeassa siinä, että tässä tehtäväsä toteutuksella ei ole merkitystä. Käsiteltäessä esimerkiksi teratavun puskuria tai laskettaessa miljoonan desimaalin pituista fibonaccin lukua onkin tilanne jo toinen. Tuota fibonaccin lukua laskettaessa rupeaakin olemaan jo merkitystä kestääkö prosessi yli 20 tuntia vai 100 millisekuntia!

Niin, alkuperäisessä tehtävässä laskettiin käyttäjän syöttämiä lukuja. Jo tuo raamattuesimerkkisi oli aika hirvittävän kaukana siitä, mihin ratkaisun tarjosin.

Ja kuten sanoin jo tuossa edellä, niin erilaisiin tilanteisiin voi olla järkevää tehdä erilainen ratkaisu. Vain idiootti kuvittelee, että sama ratkaisu on paras kaikissa tilanteissa.

Btw, tässä tulokset raamatun (33/38 käännös, joka löytyi nopeasti tekstimuodossa) sanojen laskemiselle.

GroupBy:

foreach(var g in sanat.GroupBy(s=>s))
{
    sb.Append(g.Count());
    sb.Append(' ');
    sb.AppendLine(g.Key);
}

1455514 bytes in 462-502 ms. Memory usage 108085248 bytes.

Lasketaan suoraan Dictionaryssä ("hashmap"):

var d = new Dictionary<string, int>();
foreach (var s in sanat)
{
    if (d.ContainsKey(s)) { d[s]++; } else { d[s] = 1; }
}
foreach (var g in d)
{
    sb.Append(g.Value);
    sb.Append(' ');
    sb.AppendLine(g.Key);
}

1455514 bytes in 343-424 ms. Memory usage 96428032 bytes

Eli nyt ei tarvitse luulla, kun voi tietää. Ero oli lähinnä marginaalinen. Kummassakin siis lähtökohtana, että sanat ovat taulukkona muistissa. Ajoin kummankin 5 kertaa ja otin vaihteluväliin parhaan ja huonoimman tuloksen. Toki ero muistinkulutuksen lisäyksessä (92 573 696 tavua ennen laskentaa) on suurempi, noin 4 vs 16 megatavua.

Ja tuo 1455514 tavua on siis tuloksen koko. Ilmeisesti tulos kummallakin tavalla oli sama (joskin mahdollisesti eri järjestyksessä) kun koot ovat samat.

Java8:lla

@Test
public void test() {
    // [1,2,3,1,5,9,5,3,1,2,9,7,6,3]
    List<Integer> items = Arrays.asList(1, 2, 3, 1, 5, 9, 5, 3, 1, 2, 9, 7, 6, 3);
    Map<Integer, Long> result =
            items.stream().collect(
                    Collectors.groupingBy(
                            Function.identity(), Collectors.counting()
                    )
            );
    System.out.println(result);
}

Tulostus: {1=3, 2=2, 3=3, 5=2, 6=1, 7=1, 9=2}

jalski kirjoitti:

Tuota [miljoonan desimaalin pituista] fibonaccin lukua laskettaessa rupeaakin olemaan jo merkitystä kestääkö prosessi yli 20 tuntia vai 100 millisekuntia!

Minkä takia prosessi kestäisi yli 20 tuntia? Triviaali Python-koodi (while True: a,b=b,a+b) pääsee miljoonan desimaalin pituiseen Fibonaccin lukuun muutamassa minuutissa. Luvun pituutta kannattaa seurata logaritmin tai bittimäärän avulla, koska tekstimuunnos kymmenjärjestelmään on hidasta (koneellani parikymmentä sekuntia per luku).

Metabolix kirjoitti:

(16.11.2019 09:45:54): ”– –” Minkä takia prosessi kestäisi yli 20 tuntia...

Kärjistin hiukan! Vie useampia minuutteja hitaalla koneella ja huonolla toteutuksella. Itseäni Pythonin kohdalla yllätti, että suurin osa ajasta menee luvun tulostukseen, koska muunnos vie pitkän aikaa...

jalski kirjoitti:

Itseäni Pythonin kohdalla yllätti, että suurin osa ajasta menee luvun tulostukseen, koska muunnos vie pitkän aikaa...

Ei toki suurin osa ajasta, jos tulostaa vain sen viimeisen luvun. Mutta mikä siinä yllättää? Luku on muistissa varmasti binäärimuodossa, jolloin se vie paljon vähemmän tilaa ja varsinainen laskeminen on moninkertaisesti nopeampaa kuin kymmenjärjestelmässä. Päätyminen ykkösestä tuohon miljoonan numeron lukuun Fibonaccin lukujonon peruslaskukaavalla vaatii noin 4,5 miljoonaa yhteenlaskua. Luvun muuttaminen kymmenjärjestelmään vaatii noin miljoona jakolaskua ja jakojäännöstä 10:llä, toki jaettava luku pienenee prosessin aikana.

Innostuin vielä testaamaan näitä nopeuksia. Otin testiluvut a = 11**1000000 ja b = 13**900000, jotka ovat noin miljoonan merkin mittaisia kymmenjärjestelmässä. Testasin summaa ja jakojäännöstä silmukassa ja tekstimuunnosta yksittäisenä toimenpiteenä. Alla ovat laskutoimitusten nopeussuhteet karkeassa testissäni (nopeammista silmukalla tutkittuna, viimeinen toimitus vain kerran tehtynä). Nähdään, että jakojäännös pienelläkin jakajalla on selvästi hitaampi kuin summa mutta toisaalta muunto kymmenjärjestelmään vie yhtä merkkiä kohden vähemmän aikaa kuin kokonainen pitkien lukujen summa.

jalski kirjoitti:

Kärjistin hiukan!

Jouduit kärjistämään (suomeksi valehtelemaan) että saisit edes jonkun pointin postaukseesi? :D

No joo, eipä siinä ollut pointtia edes kärjistyksen kanssa. Huono algoritmi on huono kielestä riippumatta, joskin hyvä kieli tarjoaa hyviä algoritmeja valmiina helposti käytettävässä muodossa, koska keskimääräinen koodari ei välttämättä osaa tehdä itse parempaa algoritmia ja vaikka osaisikin niin ei välttämättä ole aikaa eikä järkeä joka välissä alkaa itse koodaamaan.

Ihan samoin hyvää yleisalgoritmia pystyy kielestä riippumatta usein optimoimaan tilannekohtaisesti niissä harvinaisissa tilanteissa kun sille on tarvetta.

Joku miljoonan desimaalin fibonaccin luvun laskemisen nopeuskin on sellainen, että 99,999% ohjelmoijista sillä ei ole koskaan mitään merkitystä. (ja tuo ei ollut kärjistys, vaan arvioin että n. 200 ohjelmoijalle sillä voisi olla merkitystä)

Metabolix kirjoitti:

Ei toki suurin osa ajasta, jos tulostaa vain sen viimeisen luvun. Mutta mikä siinä yllättää? Luku on muistissa varmasti binäärimuodossa, jolloin se vie paljon vähemmän tilaa ja varsinainen laskeminen on moninkertaisesti nopeampaa kuin kymmenjärjestelmässä. Päätyminen ykkösestä tuohon miljoonan numeron lukuun Fibonaccin lukujonon peruslaskukaavalla vaatii noin 4,5 miljoonaa yhteenlaskua. Luvun muuttaminen kymmenjärjestelmään vaatii noin miljoona jakolaskua ja jakojäännöstä 10:llä, toki jaettava luku pienenee prosessin aikana.

Kyllä muunnos ja tulostus Pythonilla melko hidas on. Alla vastaavat koodit Pythonille ja 8th:lle sekä niiden suoritusajat:

import math

def fibo(n):
    if n <= 0:
        return 0
    a = 0
    b = 1
    numbits = int(math.log(n,2))
    for i in range(numbits,0,-1):
        d = a*(b*2-a)
        e = a*a+b*b
        if (n >> i) & 1:
            a = e
            b = d + e
        else:
            a = d
            b = e
    if n & 1:
        return a*a+b*b
    else:
        return a*(b*2-a)


print(fibo(4784969))

\
\ Fibonacci with million digits
\
: bits?  \ n -- nbits-1
  n:ln 2 n:ln n:/ n:int ;

: fibo-loop
  >r                             \ Put loop counter on r-stack
  \ a b
  2dup 2 n:*                     \ a b a 2b
  over n:-                       \ a b a (2b-a)
  n:* -rot                       \ d=(2b-a)*a a b
  n:sqr swap n:sqr n:+           \ d=(2b-a)*a e=b*b+a*a
  r> r@ swap n:shr 1 n:band if
    dup  \ a b b
    rot  \ b b a
    n:+  \ b c=b+a
  then ;

: fibo  \  n -- fibo(n)
  >r    \ Put n on r-stack
  F0 F1 \ a b
  ' fibo-loop 1 r@ bits? loop-
  \ a b
  r> 1 n:band if
    n:sqr swap n:sqr n:+  \ b*b+a*a
  else
    2 n:* over n:- n:*  \ (2b-a)*a
  then ;

: app:main
  4784969 fibo
  "%.f\n" strfmt \ Convert result to just an 'int' string.
  . cr
  bye ;

PS C:\temp> Measure-Command { 8th .\fibo.8th > result.txt }

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 303
Ticks             : 3034762
TotalDays         : 3.51245601851852E-06
TotalHours        : 8.42989444444444E-05
TotalMinutes      : 0.00505793666666667
TotalSeconds      : 0.3034762
TotalMilliseconds : 303.4762



PS C:\temp> Measure-Command { py .\fibo.py > result2.txt }

Days              : 0
Hours             : 0
Minutes           : 1
Seconds           : 21
Milliseconds      : 433
Ticks             : 814336733
TotalDays         : 0.000942519366898148
TotalHours        : 0.0226204648055556
TotalMinutes      : 1.35722788833333
TotalSeconds      : 81.4336733
TotalMilliseconds : 81433.6733