Last active
March 1, 2018 17:47
-
-
Save dkovacevic/62aa3c24c6d49541d72281bdc338f954 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package test; | |
| import java.util.*; | |
| public class Lotto { | |
| private static final int SIZE = 1 * 1000 * 1000; | |
| private static Random random = new Random(); | |
| private static final HashSet<Ticket> winners = new HashSet<>(); | |
| public static void main(String[] args) throws InterruptedException { | |
| System.out.printf("Generating %,d random tickets...\n", SIZE); | |
| ArrayList<Ticket> all = generateTickets(SIZE); | |
| Index index = new Index(all); | |
| Collection<Integer> raffle = raffle(); | |
| System.out.printf("Running ruffle...\n"); | |
| for (Integer number : raffle) { | |
| System.out.printf("%d, ", number); | |
| } | |
| System.out.printf("\nCalculating...\n"); | |
| long dejo = index.calculate(raffle); | |
| printDejo(all, dejo); | |
| long linear = linear(all, raffle); | |
| printShime(all, linear); | |
| } | |
| // Izvuci 7 random/distinct brojeva | |
| private static Collection<Integer> raffle() { | |
| Collection<Integer> raffle = new HashSet<>(7); | |
| while (raffle.size() < 7) { | |
| int number = randomNumber(); | |
| raffle.add(number); | |
| } | |
| return raffle; | |
| } | |
| // Generisi sve tickets | |
| private static ArrayList<Ticket> generateTickets(int size) { | |
| ArrayList<Ticket> ret = new ArrayList<>(size); | |
| for (int i = 0; i < size; i++) { | |
| ret.add(new Ticket()); | |
| } | |
| return ret; | |
| } | |
| static class Ticket extends ArrayList<Integer> { | |
| public UUID id; // unique id | |
| int shime; // number of hits calculated using linear algo | |
| int dejo; // number of hits calculated using inverted/perverted index | |
| // Listić containing 7 random numbers | |
| Ticket() { | |
| id = UUID.randomUUID(); | |
| addAll(raffle()); | |
| } | |
| @Override | |
| public int hashCode() { | |
| return id.hashCode(); | |
| } | |
| } | |
| // Generate a random number from [1-39] | |
| private static int randomNumber() { | |
| return Math.abs(random.nextInt(39) + 1); | |
| } | |
| // Class of Tickets all containing number: @number | |
| static class Group extends ArrayList<Ticket> { | |
| int watermark; | |
| Integer number; | |
| Group(Integer number) { | |
| this.number = number; | |
| } | |
| Ticket get() { | |
| return get(watermark); | |
| } | |
| void advance() { | |
| watermark++; | |
| } | |
| boolean finished() { | |
| return watermark == size() - 1; | |
| } | |
| } | |
| // Bice 39 Groups u Indexu. Jedna za svaki borj od 1..39 | |
| static class Index { | |
| private final ArrayList<Ticket> tickets; | |
| Group[] data = new Group[40]; | |
| Index(ArrayList<Ticket> tickets) { | |
| this.tickets = tickets; | |
| Date s = new Date(); | |
| for (Ticket c : tickets) { | |
| putData(c); | |
| } | |
| Date e = new Date(); | |
| long l = e.getTime() - s.getTime(); | |
| System.out.printf("Index built in: %d ms\n", l); | |
| //for(int i =1; i < 40; i++) | |
| // System.out.printf("%d: %d\n", i, get(i).size()); | |
| } | |
| // Svrstaj ovaj ticket u 7 ogovarajucih groups | |
| void putData(Ticket ticket) { | |
| for (Integer number : ticket) { | |
| Group group = data[number]; | |
| if (group == null) { | |
| group = new Group(number); | |
| data[number] = group; | |
| } | |
| group.add(ticket); | |
| } | |
| } | |
| // Uzmi 7 izvucenih Groups. Broj grupa u kojima se nalazi Listić je ujedno i broj pogodata za taj Listić | |
| // Complexity O(n) | |
| long calculate(Collection<Integer> raffle) { | |
| Date s = new Date(); | |
| /* | |
| // Za svaki izvuceni broj prebroj u koliko tickets se nalazi | |
| for (Integer number : raffle) { | |
| Group group = data[number]; | |
| for (Ticket ticket : group) { | |
| ++ticket.dejo; | |
| } | |
| */ | |
| for (Ticket ticket : tickets) { | |
| int hits = 0; | |
| for (Integer number : raffle) { | |
| Group group = data[number]; | |
| if (!group.finished() && group.get().id.equals(ticket.id)) { | |
| group.advance(); | |
| hits++; | |
| } | |
| } | |
| if (hits >= 5) { | |
| ticket.dejo = hits; | |
| winners.add(ticket); | |
| } | |
| } | |
| Date e = new Date(); | |
| return e.getTime() - s.getTime(); | |
| } | |
| } | |
| // Za svaki Listić i za svaki broj u tom listić proveri da li je bio izvucen (raffel.contains()) | |
| private static long linear(ArrayList<Ticket> all, Collection<Integer> raffle) { | |
| Date s = new Date(); | |
| for (Ticket c : all) { | |
| for (Integer number : c) { | |
| if (raffle.contains(number)) | |
| c.shime++; | |
| } | |
| } | |
| Date e = new Date(); | |
| return e.getTime() - s.getTime(); | |
| } | |
| private static void printShime(ArrayList<Ticket> all, long time) { | |
| int seven = 0; | |
| int six = 0; | |
| int five = 0; | |
| for (Ticket c : all) { | |
| seven += c.shime == 7 ? 1 : 0; | |
| six += c.shime == 6 ? 1 : 0; | |
| five += c.shime == 5 ? 1 : 0; | |
| } | |
| System.out.printf("Shime:\tSeven hits: %d, Six hits: %d, Five hits: %d in %d ms\n", seven, six, five, time); | |
| } | |
| private static void printDejo(ArrayList<Ticket> all, long time) { | |
| int seven = 0; | |
| int six = 0; | |
| int five = 0; | |
| for (Ticket c : all) { | |
| seven += c.dejo == 7 ? 1 : 0; | |
| six += c.dejo == 6 ? 1 : 0; | |
| five += c.dejo == 5 ? 1 : 0; | |
| } | |
| System.out.printf("Dejo:\tSeven hits: %d, Six hits: %d, Five hits: %d in %d ms\n", seven, six, five, time); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment