Java högsta poäng :S?

2011-10-20 20:33

Permalänk

Shimonu

Hedersmedlem ★

Plats: Linköping
Registrerad: Okt 2006

●

Skrivet av htux:

Säger inte att denna är bättre än iteration, men det är ännu en rekursiv lösning:

public static int maxScore(Player[] players) {
    return maxScore(players, 0, players.length);
}

public static int maxScore(Player[] players, int begin, int end) {
    int numPlayers = end - begin;
    if (numPlayers < 2) {
        // If only one player is left, return its score.
        return players[begin].getScore();
    } else {
        // Split the array in two parts and return the greatest of their maximum values.
        return Math.max(
        	maxScore(players, begin, end - (numPlayers / 2)),
        	maxScore(players, end - (numPlayers / 2), end)
        );
    }
}

Gå till inlägget

Den tycker jag var snygg Rekursion med lite divide and conquer

Rapportera Redigera

Citera flera Citera

2011-10-20 20:54

Permalänk

htux

Medlem

Plats: Färjestaden
Registrerad: Apr 2009

●

Skrivet av Shimonu:

Den tycker jag var snygg Rekursion med lite divide and conquer

Gå till inlägget

Tackar!

Rapportera Redigera

Citera flera Citera

2011-10-24 17:09

Permalänk

DeluxXxe

Medlem

Plats: Karlskrona
Registrerad: Feb 2007

●

Här använder jag Javas inbyggda bibliotek för sortering av collections.

http://pastie.org/2750922

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class aaa {
  private static class Player {
    int score;
    Player(int score) {
      this.score = score;
    }
  }
  public static void main(String[] args) {
    Player[] players = new Player[] { new Player(3), new Player(11), new Player(8) };
    Collections.sort(Arrays.asList(players), new Comparator<Player>() { 
    @Override
      public int compare(Player o1, Player o2) {
        return o1.score < o2.score ? 1 : 0;
      }
    });
    System.out.println(players[0].score);
  }
}

Visa signatur

Phenom X6 1045T | Corsair TWIN2X PC6400C4DHX 2x2GB + Crucial Ballistix Sport 2x2GB | Gigabyte ma785gmt-us2h | Silverstone Temjin 08 | Corsair VX450

Rapportera Redigera

Citera flera Citera

2011-10-25 10:31

Permalänk

DeluxXxe

Medlem

Plats: Karlskrona
Registrerad: Feb 2007

●

Jag integrerade samtliga lösningar i tråden och gjorde en prestandajämförelse. Här är koden: http://pastie.org/2754986

Vanlig loopning var snabbast, medan mitt exempel med comparator var slöast. Får väl trösta mej med att mitt gick snabbast att skriva.

Här är resultat, för den som inte vill exekvera koden:

usingComparator 947048nanoseconds, with score28
recursiveMultiLine 30032nanoseconds, with score28
looping 1536nanoseconds, with score28
singleLineRecursive 2723nanoseconds, with score28
usingMath 1886nanoseconds, with score28

Det blev 100 rader kod totalt, så kika på pastie länken istället för att jag ska smutsa ner hela sidan här på Swec.

Visa signatur

Phenom X6 1045T | Corsair TWIN2X PC6400C4DHX 2x2GB + Crucial Ballistix Sport 2x2GB | Gigabyte ma785gmt-us2h | Silverstone Temjin 08 | Corsair VX450

Rapportera Redigera

Citera flera Citera

2011-10-25 10:45

Permalänk

andelf

Medlem

Plats: umeå
Registrerad: Maj 2004

●

Skrivet av DeluxXxe:

Jag integrerade samtliga lösningar i tråden och gjorde en prestandajämförelse. Här är koden: http://pastie.org/2754986

Vanlig loopning var snabbast, medan mitt exempel med comparator var slöast. Får väl trösta mej med att mitt gick snabbast att skriva.

Här är resultat, för den som inte vill exekvera koden:

usingComparator 947048nanoseconds, with score28
recursiveMultiLine 30032nanoseconds, with score28
looping 1536nanoseconds, with score28
singleLineRecursive 2723nanoseconds, with score28
usingMath 1886nanoseconds, with score28

Det blev 100 rader kod totalt, så kika på pastie länken istället för att jag ska smutsa ner hela sidan här på Swec.

Gå till inlägget

snyggt +1 på den

Rapportera Redigera

Citera flera Citera

2011-10-26 10:33

Permalänk

Raz

Medlem

Plats: Helvetet
Registrerad: Jul 2001

●

Skrivet av DeluxXxe:

Jag integrerade samtliga lösningar i tråden och gjorde en prestandajämförelse. Här är koden: http://pastie.org/2754986

Vanlig loopning var snabbast, medan mitt exempel med comparator var slöast. Får väl trösta mej med att mitt gick snabbast att skriva.

Här är resultat, för den som inte vill exekvera koden:

usingComparator 947048nanoseconds, with score28
recursiveMultiLine 30032nanoseconds, with score28
looping 1536nanoseconds, with score28
singleLineRecursive 2723nanoseconds, with score28
usingMath 1886nanoseconds, with score28

Det blev 100 rader kod totalt, så kika på pastie länken istället för att jag ska smutsa ner hela sidan här på Swec.

Gå till inlägget

Tyckte antalet testfall var lite svagt, så fixade till lite åt dig
http://pastie.org/2760801

Result for 40000 players

usingComparator 18826291nanoseconds, with score99988
recursiveMultiLine 2308253nanoseconds, with score99988
looping 462921nanoseconds, with score99988
singleLineRecursive 1175146nanoseconds, with score99988
usingMath 761108nanoseconds, with score99988

Visa signatur

Min nästan hemliga sida Ancilla, face mea laganum!
Jag har sjukast drömmar. Det ligger i min natur att avsiktligt tolka felaktigheter fel.
00:17 < sphr> Raz^ jag spenderade 4h med att slita bort punghåren för hand

Rapportera Redigera

Citera flera Citera

Java högsta poäng :S?

Externa nyheter

Spelnyheter från FZ