Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Nov 2013

Kent-buggen

Länken till problemet

Vi får rätt på 7 av 16 testcases.
Maxtid för problemet är 6 sekunder och så som programmet ser ut nu ligger vi över den gränsen.

public class Kent { static Kattio io = new Kattio(System.in, System.out); public static void main(String[] args) { List<String> skit = new ArrayList<String>(); int z = io.getInt(); for(int i = 0; i < z; i++) { skit.add(io.getWord()); } String temp = ""; int dubles = 0; boolean sant = true; int q = 1; for(int i = 1; i < skit.size(); i++) { temp = skit.get(i); while(skit.contains(temp) && q < skit.size()) { skit.set(i , ""); q++; if(skit.contains(temp) && sant) { dubles++; sant=false; } } } System.out.println(dubles); } }

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jan 2007

Känns väl kanske mer effektivt att sortera listan i bokstavsordning först, med någon lämplig metod. Sedan kan man gå igenom listan lite mer effektivt och jämföra element n med n+1 (och n+2, n+3 etc om samma namn finns fler än två gånger) för att hitta dubbletter

Core i7 7700K | Titan X (Pascal) | MSI 270I Gaming Pro Carbon | 32 GiB Corsair Vengeance LPX @3000MHz | Samsung 960 EVO 1TB

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jan 2014

Som gammal KTH-student vill jag fråga om uppgiften hör till en kurs (och därmed är betygsgrundande). I så fall bör hederskodex appliceras då uppgiften är tänkt att lösas individuellt och inte outsourcas.

Är det däremot tänkt som träning för personlig utveckling så kör på

Trädvy Permalänk
Webbutvecklare
Moderator
Plats
::1
Registrerad
Dec 2002
  1. Vare sig det här är en skoluppgift eller en personlig utmaning så bör du se över dina variabelnamn; i det förstnämnda fallet är det inte otänkbart att du får avdrag för att ha kallat dina variabler skit, z, dubles, sant och q. Respektera andra som ska läsa koden (det inkuderar ditt framtida jag och eventuella lärare) och demonstrera att du har en klar bild av problemet genom korrekt, lättläst namngivning och formatering.

  2. Den föreslagna lösningen itererar listan onödigt många gånger. Fundera på hur ArrayList.contains() kan vara implementerad och vad det har för konsekvens för din tidsåtgång. Tips: Du kan lösa problemet helt utan varken det eller att sortera din input.

Abstractions all the way down.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jun 2015

Var tvungen att testa.. vann på python2 med 10 rader

VR: Oculus Rift CV1 + Touch
Dator: i5-4690K @ 4.5 GHz | Crucial 16GB 1600 | MSI 100ME GTX 970 | Samung 850 SSD 250GB | Corsair RM550 | Win10 | FD Define R5 | Noctua D15
Server: Pentium g3258 | Crucial 16GB 1600 | 2x3TB 120gb Cache ZFS | Corsair CX430 | Ubuntu Server | FD Node 304 | Cooler Master Hyper 212 Evo

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jan 2014
Skrivet av ehallq:

Var tvungen att testa.. vann på python2 med 10 rader

Blev också tvungen att testa bara för det, vann Java med 16 rader

0.60 tid!

Som sagt, om TS bekräftar att detta inte är skoluppgift så kan du få en hint (även om väldigt bra hint redan givits i tråden)

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Nov 2013

@Foffi:
Detta har inget med skolan att göra. I skolan pysslar vi fortfarande med spara heltal som integer.

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Dec 2008

Nu blev det tävling

I C++ kommer jag också ner till 16 rader när jag fular lite (man måste ju skriva så mycket include-direktiv och deklarationer så man ser knappt koden), men den identifierar dubletter bland 100000 slumpmässiga 20-teckens strängar (bandnamn? Hur många lyssnar på ikejpjnsrxhukrgjtqxo?) på 0.02 sekunder på min i7-4770.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jan 2014
Skrivet av Ingetledigtnamn:

Nu blev det tävling

I C++ kommer jag också ner till 16 rader när jag fular lite (man måste ju skriva så mycket include-direktiv och deklarationer så man ser knappt koden), men den identifierar dubletter bland 100000 slumpmässiga 20-teckens strängar (bandnamn? Hur många lyssnar på ikejpjnsrxhukrgjtqxo?) på 0.02 sekunder på min i7-4770.

Java är alltid långsammare pga att det är en VM. Ville bara säga det. Och sen är det resultat på Kattis som gäller

Skrivet av ericeric113:

@Foffi:
Detta har inget med skolan att göra. I skolan pysslar vi fortfarande med spara heltal som integer.

Okej, i så fall, tänk över om ArrayList verkligen är rätt ställe att lagra inlästa namn på. Dess contains(...) funktion är väldigt långsam (linjär tidskomplexitet O(n), om du har börjat med sånt än), vilket inte är snabbt nog för detta fall.

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Dec 2008
Skrivet av Foffi:

Och sen är det resultat på Kattis som gäller

Ok, då. 0.20s på Kattis. Med så korta körtider är det ganska mycket slump med i körtiden. Det beror en hel på vad maskinen gör i övrigt.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jan 2014
Skrivet av Ingetledigtnamn:

Ok, då. 0.20s på Kattis. Med så korta körtider är det ganska mycket slump med i körtiden. Det beror en hel på vad maskinen gör i övrigt.

Ja, typiskt bra om man ligger precis på gränsen med tiden kan vara att testa skicka in mellan 3-5 på natten. Då kan man spara några millisekunder. Men det brukar inte variera så speciellt mycket faktiskt, är stabilt. Finns en kö och sånt modernt, så den kör bara en uppgift per tråd i taget.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Nov 2013

@Foffi:
Kanske en dum fråga men syftar du på att vi ska spara det i en Array ist?

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jun 2015

Python2. 0.15s

11 rader, missade importraden när jag räknade

import sys list = {} hit = 0 for line in sys.stdin: try: list[line] = list[line] + 1 if list[line] == 2: hit = hit +1 except KeyError: list[line] = 1 print hit

VR: Oculus Rift CV1 + Touch
Dator: i5-4690K @ 4.5 GHz | Crucial 16GB 1600 | MSI 100ME GTX 970 | Samung 850 SSD 250GB | Corsair RM550 | Win10 | FD Define R5 | Noctua D15
Server: Pentium g3258 | Crucial 16GB 1600 | 2x3TB 120gb Cache ZFS | Corsair CX430 | Ubuntu Server | FD Node 304 | Cooler Master Hyper 212 Evo

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Dec 2008

@ehallq:

Kika på vad defaultdict gör och se om du kan krympa lite till.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jun 2015
Skrivet av Ingetledigtnamn:

@ehallq:

Kika på vad defaultdict gör och se om du kan krympa lite till.

Tack, blev 8 rader, men dock 0.16-0.19s (varierar från körning till körning upptäckte jag.

import sys, collections list = collections.defaultdict(int) hit = 0 for line in sys.stdin: list[line] += 1 if list[line] == 2: hit += 1 print hit

Testade min gamla kod igen ersatte a = a +1 delarna med += (spelar nog ingen roll) dock. Fick ner det till 0.14s (kan bero på slumpen)

import sys list = {} hit = 0 for line in sys.stdin: try: list[line] += 1 if list[line] == 2: hit += 1 except KeyError: list[line] = 1 print hit

VR: Oculus Rift CV1 + Touch
Dator: i5-4690K @ 4.5 GHz | Crucial 16GB 1600 | MSI 100ME GTX 970 | Samung 850 SSD 250GB | Corsair RM550 | Win10 | FD Define R5 | Noctua D15
Server: Pentium g3258 | Crucial 16GB 1600 | 2x3TB 120gb Cache ZFS | Corsair CX430 | Ubuntu Server | FD Node 304 | Cooler Master Hyper 212 Evo

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jan 2014
Skrivet av ericeric113:

@Foffi:
Kanske en dum fråga men syftar du på att vi ska spara det i en Array ist?

Nej, en array har också linjär uppslagstid. Med detta menas: i värsta fall måste du gå igenom alla element i listan (då det sökta elementet ligger sist i listan). I din kod så kan detta inträffa hela tiden, att du ständigt måste söka dig fram i listan. Contains på en vanlig lista är en loop över varje element, där den kollar om a.equals(b), där a är elementet du letar efter, och b är det nuvarande elementet i listan.
Man går alltså igenom varje element i tur och ordning och jämför med det sökta, helt enkelt.

Det du vill hitta är en datastruktur som inte har denna utformningen... Som alltså kan göra en uppslagning på konstant tid. På så sätt växer inte söktiden i contains(...) metoden när storleken på listan växer.

Då jag inser att detta kanske är överkurs just nu så föreslår jag rakt av att du läser igenom hur ett Set fungerar.

Trädvy Permalänk
Medlem
Plats
Skellefteå
Registrerad
Okt 2008
Skrivet av ericeric113:

@Foffi:
Kanske en dum fråga men syftar du på att vi ska spara det i en Array ist?

Det finns en annan datastruktur än array som är betydligt mer lämpad för uppgiften, men om du aldrig stött på den förut så är det förstås omöjligt för dig att känna till den.

1800X, 1080 SLI, 4K

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Nov 2013

@Foffi:
Alltså en HashMap??

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jan 2014
Skrivet av ericeric113:

@Foffi:
Alltså en HashMap??

Kanske det, testa och se hur det funkar

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jun 2015

Testade i C++ samma princip som i python. Dock fick jag bästa tiden på 0.29s

#include <map> #include <string> #include <iostream> using namespace std; map<string, int > dictionary; int main(void) { string a; int hit = 0; while (cin >> a) try { dictionary[a]++; if(dictionary[a] == 2) { hit++; } } catch (int e) { dictionary[a] = 1; } cout << hit << endl; return 0; }

VR: Oculus Rift CV1 + Touch
Dator: i5-4690K @ 4.5 GHz | Crucial 16GB 1600 | MSI 100ME GTX 970 | Samung 850 SSD 250GB | Corsair RM550 | Win10 | FD Define R5 | Noctua D15
Server: Pentium g3258 | Crucial 16GB 1600 | 2x3TB 120gb Cache ZFS | Corsair CX430 | Ubuntu Server | FD Node 304 | Cooler Master Hyper 212 Evo

Trädvy Permalänk
Medlem
Plats
London / Göteborg
Registrerad
Jul 2007
Skrivet av Foffi:

Blev också tvungen att testa bara för det, vann Java med 16 rader

0.60 tid!

Som sagt, om TS bekräftar att detta inte är skoluppgift så kan du få en hint (även om väldigt bra hint redan givits i tråden)

0.13s med C#, 12 SLOC enligt Visual Studios sätt att räkna.

Var bara tvungen jag med

WS: Bärbar workstation, 2 * Dell U2412M
HTPC: Intel NUC, Canton GLE 496, Yamaha RV-A830, Sanyo PLV-Z700
Server: Intel Xeon E3-1240@3.4 GHz, ESXi, 16GB RAM, 8*2TB RAID-Z2 + SSD-cache
Slösurf: MacBook Air 11,6", Nokia Lumia 925, OnePlus Two
Kamera: Canon EOS 5DII + 1DIII, Canon 100/2.8 Macro, Canon 70-200/2.8L, Canon 24-70/2.8L

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Dec 2008
Skrivet av ehallq:

Tack, blev 8 rader, men dock 0.16-0.19s (varierar från körning till körning upptäckte jag.

Nu fuskar du ju eftersom du inte bryr dig om den inledande siffran som talar on hur många namn det är, men vill du kan du hyvla några rader till genom att flytta räknandet till utskriften. Det blir kanske inte helt lätt att förstå, men det blir kortare.

import sys, collections list = collections.defaultdict(int) for line in sys.stdin: list[line] += 1 print sum([1 for x in list.values() if x > 1])

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2006

Hade tydligen redan löst den. 0,17s i Python 2.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jan 2014

Känns som att denna tråden har frångått poängen lite, som var att ge TS hjälp (utan att säga exakt hur han ska göra), till att försöka skriva så optimal kod som möjligt... Låt TS lösa detta själv och ge endast vägledande hjälp, om inget annat efterfrågas. Så lär man sig bäst!

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Dec 2008

@Foffi:

Tråden spårade ur lite, där håller jag med (de spårar ofta ur på sweclockers, jag vet inte varför...). Men jag tror inte att jag spoilade TS inlärning genom att tipsa ehallq om finesser i Python. TS har inte någon större nytta av list comprehensions då han valt ett annat språk. Men jag håller med, vägled utan att posta färdig kod.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jan 2014

@Ingetledigtnamn:

Nu har vi många olika språk representerade, saknas bara Java, så jag tänkte jag skriver det innan det kommer

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2006
Skrivet av Ingetledigtnamn:

Nu fuskar du ju eftersom du inte bryr dig om den inledande siffran som talar on hur många namn det är, men vill du kan du hyvla några rader till genom att flytta räknandet till utskriften. Det blir kanske inte helt lätt att förstå, men det blir kortare.

import sys, collections list = collections.defaultdict(int) for line in sys.stdin: list[line] += 1 print sum([1 for x in list.values() if x > 1])

For-loopen går ju bra att skriva på en rad...

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Dec 2008

Jo, det kan krympas mer, men

import sys, collections print sum([1 for x in collections.Counter([l for l in sys.stdin]).values() if x > 1])

är inte så läsbart.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2006

Jag tycker det är rätt läsbart ändå.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Jun 2015
Skrivet av Ingetledigtnamn:

Nu fuskar du ju eftersom du inte bryr dig om den inledande siffran som talar on hur många namn det är, men vill du kan du hyvla några rader till genom att flytta räknandet till utskriften. Det blir kanske inte helt lätt att förstå, men det blir kortare.

import sys, collections list = collections.defaultdict(int) for line in sys.stdin: list[line] += 1 print sum([1 for x in list.values() if x > 1])

Är väl inte fusk, jag anser att det är överflödig information som inte behöver vara med

Skrivet av eurythmech:

For-loopen går ju bra att skriva på en rad...

Skrivet av Ingetledigtnamn:

Jo, det kan krympas mer, men

import sys, collections print sum([1 for x in collections.Counter([l for l in sys.stdin]).values() if x > 1])

är inte så läsbart.

Klart allt går att skriva ner på en rad, men tänkte mest att man skriver det på "standardform"

VR: Oculus Rift CV1 + Touch
Dator: i5-4690K @ 4.5 GHz | Crucial 16GB 1600 | MSI 100ME GTX 970 | Samung 850 SSD 250GB | Corsair RM550 | Win10 | FD Define R5 | Noctua D15
Server: Pentium g3258 | Crucial 16GB 1600 | 2x3TB 120gb Cache ZFS | Corsair CX430 | Ubuntu Server | FD Node 304 | Cooler Master Hyper 212 Evo