Optymalizacja kolejnego algorytmu

Tym razem probuje napisac algorytm do tego zadania: http://pl.spoj.pl/problems/NAMES/

Probowalem zoptymalizowac na kazdy sposob jaki mi tylko przyszedl do glowy, juz na kilkanascie roznych sposobow.

Najszybsze rozwiazanie jakie udalo mi sie napisac bylo takie:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
	
	class Main {
	    
		private static class Sort implements Comparator<String> {
			
			public int compare(String i1, String i2) {
				String[] t1=i1.split(" ");
				String[] t2=i2.split(" ");
				int i=Integer.parseInt(t1[1]);
				int j=Integer.parseInt(t2[1]);
				int k=j-i;
				if(k!=0) return k;
				else return t1[0].compareTo(t1[0]);
			}
			
		}
		
		public static void main(String[] args) throws IOException {
			
			BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
			String slowo=" ";
			Map<String, Integer> licznik = new TreeMap<String, Integer>();
			while(slowo!=null) {
				slowo=br.readLine();
				if(slowo!=null && slowo.length()>1) {
				slowo=slowo.split(" ")[2].toUpperCase();
				if(licznik.get(slowo)!=null) {
				int ilosc=licznik.get(slowo)+1;			
				licznik.remove(slowo);
				licznik.put(slowo, ilosc);
				}
				else licznik.put(slowo, 1);
				}
			}
			Collection imiona=licznik.keySet();
			Collection ilosci=licznik.values();
			Iterator it=imiona.iterator();
			Iterator it2=ilosci.iterator();
			Collection<String> lista=new ArrayList<String>();
			for(int i=0; i<imiona.size(); i++) {
				lista.add(it.next()+" "+it2.next());
			}
			Collections.sort((ArrayList<String>) lista,new Sort());
			for(String s: lista) System.out.println(s);
		}
		
	}

Jednak jest zbyt wolne. Jesli bym nie musial sortowac na koniec wg. ilosc wystapien (czyli wg. wartosci kluczy) to bym sie w czasie miescil, ale niestety jakos to posortowac musze, jednak po takim sortowaniu przekraczam limit czasu. Moze wiec da sie jakos szybciej to posortowac?

Probowalem tez inaczej.

Zrobilem rowniez cos takiego jak ponizej ale wciaz za wolne:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Iterator;
import java.util.TreeSet;

class Main {

private static class Imie<Typ1, Typ2> implements Comparable<Imie<Typ1,Typ2>> {

	protected Typ1 nazwa;
	protected Typ2 ilosc;
	
	public Imie(String nazwa, int ilosc) {
		this.nazwa=(Typ1) nazwa;
		this.ilosc=(Typ2) String.valueOf(ilosc);
	}
	
	public void zwieksz() {
		int il=Integer.parseInt((String) ilosc);
		il++;
		ilosc=(Typ2) String.valueOf(il);
	}
	
	public int compareTo(Imie<Typ1, Typ2> o) {
		int il=Integer.parseInt((String) ilosc);
		int il2=Integer.parseInt((String) o.ilosc);
		return il2-il!=0?il2-il:((String) nazwa).compareTo((String) o.nazwa);
	}
	
	public boolean equals(Object o) {
		return ((String) nazwa).equals((String) ((Imie<String,Integer>) o).nazwa);
	}
	
	public int getIlosc() {
		return Integer.parseInt((String) ilosc);
	}
	
	public String toString() {
		return (String) nazwa+" "+getIlosc();
	}
	
}

public static void main(String[] args) throws IOException {

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String slowo=" ";
Collection<Imie<String,Integer>> licznik=new TreeSet<Imie<String,Integer>>(); 
while(slowo!=null) {
slowo=br.readLine();
if(slowo!=null && slowo.length()>1) {
slowo=slowo.split(" ")[2].toUpperCase();
Imie<String,Integer> nowe=new Imie<String,Integer>(slowo,1);
Iterator<Imie<String,Integer>> it =licznik.iterator();
boolean dalej=true;
while(it.hasNext() && dalej) {
	Imie<String,Integer> imie=it.next();
	if(imie.equals(nowe)) {
		imie.zwieksz();
		licznik.add(imie);
		dalej=false;
	}
}
if(dalej) licznik.add(nowe);
}

}
for(Imie<String,Integer> s: licznik) System.out.println(s);
}

}

Moj ostatni pomysl byl taki:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;
 
class Imie implements Comparable<Imie> {
  String imie;
  int n;
  public Imie(String imie, int ilosc) {
	  this.imie=imie;
	  n=ilosc;
  }
  
  public Imie(Imie im) {
	  imie=im.imie;
	  n=im.n;
  }
  
  void zwieksz() {
	  n++;
  }

public int compareTo(Imie imtor) {
	return imtor.n-n==0?imie.compareToIgnoreCase(imtor.imie):imtor.n-n;
}

public boolean equals(Object o) {
	return ((Imie) o).imie.equalsIgnoreCase(imie);
}

public String toString() {
	return imie.toUpperCase()+" "+n;
}
 
}
 
class Main {
 
  public static void main(String[] args) {
    Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    Collection<Imie> lista=new TreeSet<Imie>();
    while(s.hasNext()) {
    	s.next();
    	s.next();
    	Imie nowy=new Imie(s.next(),1);
    	Iterator<Imie> it=lista.iterator();
    	boolean dalej=true;
    	while(it.hasNext() && dalej) {
    		Imie next=it.next();
    		if(next.equals(nowy)) {
    			nowy=new Imie(next);
    			nowy.zwieksz();
    			dalej=false;
    			it.remove();
    		}
    		else if(next.imie.compareTo(nowy.imie)>0) dalej=false;
    	}
    	lista.add(nowy);
    }
    for(Imie im: lista) System.out.println(im);
  }
}

Innym pomyslem bylo wykorzystanie interfejsu Map w sposob nastepujacy (jednak wydaje mi sie on juz zbyt przekombinowany i wolny):

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeSet;
 
class Imie implements Comparable<Imie> {
  Map<String,Integer> im;
  public Imie(String imie, int ilosc) {
	  im=new HashMap<String,Integer>();
	  im.put(imie, ilosc);
  }
  
  public Imie(Imie imie) {
	  im=imie.im;
  }
  
  void zwieksz() {
	  int n=im.values().iterator().next();
	  String i=im.keySet().iterator().next();
	  im.clear();
	  im.put(i,n+1);
  }

public int compareTo(Imie imie) {
	int i=im.values().iterator().next();
	int i2=imie.im.values().iterator().next();
	return i2-i==0?im.keySet().iterator().next().compareTo(imie.im.keySet().iterator().next()):i2-i;
}

public boolean equals(Object o) {
	return ((Imie) o).im.keySet().iterator().next().equalsIgnoreCase(im.keySet().iterator().next());
}

public int porownanie(Imie imie) {
	return im.keySet().iterator().next().compareTo(imie.im.keySet().iterator().next());
}

public String toString() {
	return im.keySet().iterator().next().toUpperCase()+" "+im.values().iterator().next();
}
 
}
 
class Main {
 
  public static void main(String[] args) {
    Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    Collection<Imie> lista=new TreeSet<Imie>();
    while(s.hasNext()) {
    	s.next();
    	s.next();
    	Imie nowy=new Imie(s.next(),1);
    	Iterator<Imie> it=lista.iterator();
    	boolean dalej=true;
    	while(it.hasNext() && dalej) {
    		Imie next=it.next();
    		if(next.equals(nowy)) {
    			nowy=new Imie(next);
    			nowy.zwieksz();
    			dalej=false;
    			it.remove();
    		}
    		else if(next.porownanie(nowy)>0) dalej=false;
    	}
    	lista.add(nowy);
    }
    for(Imie im: lista) System.out.println(im);
  }
}

Jaja sobie robisz? o_O
Czytasz wejście i wrzucasz wszystko do mapy która mapuje stringi na ilość ich wystąpień. To jest zadanie na 10 linijek...

edit: Challenge accepted:

import sys
import re
from operator import itemgetter
mapa={};
for line in sys.stdin.readlines():
    name = re.match("\w+\\. \w+ (\w+)", line).group(1).upper();
    mapa[name]=mapa[name]+1 if mapa.get(name)!=None else 1
sorted = sorted(mapa.items(), key=itemgetter(1),reverse=True)
for key,value in sorted:
    print key,value

W javie byłoby trochę dłuższe, ale bez przesady...
Ja bym w javie tu brał po prostu Map<String,Integer> i posortował ją za pomocą

List<Entry<String, Integer>> entriesList = new LinkedList<Entry<String, Integer>>(wordsMap.entrySet());
Collections.sort(entriesList, new MapValueComparator());

a komparator byłby pewnie taki:

public class MapValueComparator implements Comparator<Entry<String, Integer>> {

    @Override
    public int compare(Entry<String, Integer> f, Entry<String, Integer> s) {
        if(!s.getValue().equals(f.getValue()){
          return s.getValue().compareTo(f.getValue());
        }else{
          return s.getKey().compareTo(f.getKey()); //albo odwrotnie, nie chce mi się sprawdzać
        }
    }
}

edit:
trochę lepsza wersja pytona:

import sys
import re
from operator import itemgetter
from collections import defaultdict
def code():
    mapa=defaultdict(int)
    matcher = re.match
    readline = sys.stdin.readlines 
    up = str.upper
    for line in readline():
        mapa[up(matcher("\w+\\. \w+ (\w+)",line).group(1))]+= 1
    sortedList = sorted(mapa.items(), key=itemgetter(1),reverse=True)
    for key,value in sortedList:
        print key,value
code();

Przekraczam dalej limit czasu, kod wyglada tak:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;


class Main {

    public static class MapValueComparator implements Comparator<Entry<String, Integer>> {
		 
	    @Override
	    public int compare(Entry<String, Integer> f, Entry<String, Integer> s) {
	        if(!s.getValue().equals(f.getValue())){
	          return s.getValue().compareTo(f.getValue());
	        }else{
	          return f.getKey().compareTo(s.getKey()); //albo odwrotnie, nie chce mi się sprawdzać
	        }
	    }
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String slowo=" ";
		Map<String, Integer> licznik = new HashMap<String, Integer>();
		while(slowo!=null) {
		slowo=br.readLine();
		if(slowo!=null && slowo.length()>1) {
		slowo=slowo.split(" ")[2].toUpperCase();
		if(licznik.get(slowo)!=null) {
		int ilosc=licznik.get(slowo)+1;
		licznik.remove(slowo);
		licznik.put(slowo, ilosc);
		}
		else licznik.put(slowo, 1);
		}
		}
		List<Entry<String, Integer>> entriesList = new LinkedList<Entry<String, Integer>>(licznik.entrySet());
		Collections.sort(entriesList, new MapValueComparator());
		for(Entry<String,Integer> s: entriesList) System.out.println(s.getKey()+" "+s.getValue());
	}
	
}

Zamień tą lodówkę w której piszesz na coś co formatuje kod. Oczywiste spowalniacze:

   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String slowo = " ";
        Map<String, Integer> licznik = new HashMap<String, Integer>();
        while (slowo != null) {
            slowo = br.readLine();
            if (slowo != null) {
                slowo = slowo.split(" ")[2].toUpperCase();
                Integer ilosc = licznik.get(slowo);
                if (ilosc!=null) {
                    licznik.put(slowo, ilosc+1);
                } else
                    licznik.put(slowo, 1);
            }
        }
        List<Entry<String, Integer>> entriesList = new LinkedList<Entry<String, Integer>>(licznik.entrySet());
        Collections.sort(entriesList, new MapValueComparator());
        StringBuffer sb = new StringBuffer();
        for (Entry<String, Integer> s : entriesList){
            sb.append(s.getKey());
            sb.append(" ");
            sb.append(s.getValue());
            sb.append("\n");
        }
        System.out.print(sb.toString());

Według mnie należy:

1. Przypisać każdemu wejściowemu id, tak żeby te same i tylko te same nazwiska miały takie samo id, za pomocą HashMapy,
2. Następnie zrobić zliczanie najczęściej występujących id liniowo,
3. Następnie liniowo pogrupować id względem częstotliwości,
4. Następnie w każdej grupie posortować id względem porządku leksykograficznego reprezentowanych przez nie nazwisk, tutaj złożoność O(n lg n) dla każdego segmentu idków,
5. Na koniec oczywiście wypisywanie w odpowiedniej kolejności, liniowo,

Ogólnie trochę zabawy jest. Jest już późno i nie myślę już dobrze, więc sobie daruję to raczej :)

A coś takiego:

1. wczytać wyłącznie imiona i zapisać w postaci kilku list (+zmiana liter na duże, a->A), pierwsza z imionami zaczynającymi się na literę A, druga na literę B itd.

2. dla pierwszego imienia z listy na A A(lista) przeszukać listę zliczając i usuwając wystąpienia tego imienia, wynik zapisać do tablicy z wynikami w postaci [imię , ilość wystąpień]

3. powtórzyć pkt 2 dla drugiego imienia z listy A(lista) zliczając i usuwając wystąpienia drugiego imienia i zapisując wynik do tablicy Wynikowej

4. itd. dla imion na B, C ... w B(lista) , C(lista) ...

5. na koniec posortować tablicę z Wynikami i wydrukować.

Idea tego rozwiązania jest taka, że im więcej imion się zliczy tym mniejsza pozostaje lista do przeszukiwania.

A jak komuś bardzo zależy, to może przygotować listę popularnych imion żeby w pierwszych przebiegach wyciąć jak najwięcej elementów z przeszukiwanej listy. Rozwiązanie trochę mało eleganckie ale może być w tym przypadku bardzo skuteczne :)

Jest gdzieś napisane, że dane mają w jakikolwiek sposób być powiązane z rzeczywistością? Moim zdaniem bardzo dobrze mogą wstawić ciąg imion typu:
allsgkjer
aglsdjker
agljk
agoj
...
awegoui

• gdzieś w środku 10 % "imion" nie zaczynających się na 'a'.

Można by się też pobawić w skompresowane drzewo trie (tzw drzewo Patricia). Niekoniecznie musiałoby być to wolniejsze albo szybsze, szczególnie że nie znamy danych testowych, więc nie ma jak przewidzieć.

Wibowit tylko czy to rozwiazanie na pewno bedzie szybsze? I dlaczego akurat nazwisko, a nie imie?

997 - probowalem cos takiego tez, ale bylo rowniez za wolne.

Spędziłem nad tym stanowczo za dużo czasu, ale po zamianie kolejności wypisywania wyjście działa ;)

import sys,collections
def code():
	d=collections.defaultdict(int)
	for line in sys.stdin: d[str.upper(line.split()[2])]-=1
	for i,w in sorted((i,w) for w,i in d.iteritems()): print w,-i
code()

Edit: po chamie dwie linie mniej.

1. Walnąłem się, nie nazwiska a imiona oczywiście.
2. Czy na pewno szybsze? Nie wiadomo, ale jest duża szansa że tak. Obecnie sortujesz raz całą tablicę, a więc złożoność z grubsza O(n lg n). Jeśli dane zostaną podzielone linowym algorytmem na kubełki to złożoność będzie typu O(n * średni lg z rozmiaru kubełka). Jeśli średni rozmiar kubełka będzie mały, to zysk może być duży. W przypadkach skrajnych, np wszystkie imiona unikalne, będzie jeden kubełek, a wiec zysk żaden, a nawet lekka (pomijalna?) strata.

Pomysł ze skompresowanym drzewem trie można by zaimplementować w taki sposób, aby osiągnąć złożoność liniową - dla podanych założeń, czyli alfabet o stałym rozmiarze i stałe ograniczenie na długość nazwiska jest to jak najbardziej możliwe. Podobnie sortowanie pozycyjne miałoby tutaj złożoność liniową. Przy sortowaniu pozycyjnym mozna by zastosować trik i np ładować po 3 znaki do shorta - jeden znak to tutaj < 32 możliwości, czyli 5 bitów informacji. W shorcie spokojnie zmieści się 3 * 5 bitów = 15 bitów bez większego kombinowania.

Można by połączyć nawet dzielenie linowym algorytmem na kubełki z sortowaniem pozycyjnym kubełków z podanym przeze mnie przed chwilą trikiem.

Chyba sprobuje jeszcze na tym drzewie jutro to zrobic.

Poki co wyprobowalem w ten sposob:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;


class Main {

    public static void main(String[] args) throws IOException {
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	PrintWriter out=new PrintWriter(System.out);
	String slowo=" ";
	Map<String, Integer> licznik = new HashMap<String, Integer>();
	int max=0;
	while(slowo!=null) {
		slowo=br.readLine();
		if(slowo!=null && slowo.length()>1) {
		slowo=slowo.split(" ")[2].toUpperCase();
		if(licznik.get(slowo)!=null) {
		int ilosc=licznik.get(slowo)+1;
		if(ilosc>max) max=ilosc;
		licznik.remove(slowo);
		licznik.put(slowo, ilosc);
		}
		else {
			licznik.put(slowo, 1);
			if(max<1) max=1;
		}
		}
	}
	Collection<String>[] imiona=new ArrayList[max];
	for(Entry<String, Integer> ent: licznik.entrySet()) {
		int val=max-ent.getValue();
		if(imiona[val]==null) imiona[val]=new ArrayList<String>();
		imiona[val].add(ent.getKey());
	}
	for(int i=0; i<max; i++) {
		Collections.sort((ArrayList) imiona[i]);
		int n=max-i;
		for(String s: imiona[i]) out.println(s+" "+n);
	}
	out.flush();
	}
	
}

ale dostaje blad wykonania na SPOJ-u :/ Dla danych testowych jest ok. Nie bardzo rozumeim dlaczego dostaje blad wykonania.