Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3430
Herkunft: Trier -> München

beantworten | zitieren | melden

Hallo,

hier die neue Aufgabe, mal was ganz kurzes:

mit der im Code gegeben Klasse sollen 10 Werte zwischen -31 und 31 über einen Indexer abgelegt und wieder ausgelesen werden können.
Ergänzt die Klasse ausschliesslich an den markierten Stellen um jeweils ein einziges Statement, damit der Indexer funktioniert.

Es dürfen nur die beiden Statements eingebaut werden, weiter Änderungen oder Ergänzungen sind nicht erlaubt.

Gruß, MarsStein

using System;

public class MultiValue31
{
  long val;
  
  public sbyte this[int idx]
  {
    get
    {
      if((idx < 0) || (idx > 9))
      {
        throw new IndexOutOfRangeException("index muss im Intervall [0;9] liegen");
      }
      
      return /* hier das Statement für den Getter */;
    }
    set
    {
      if((idx < 0) || (idx > 9))
      {
        throw new IndexOutOfRangeException("index muss im Intervall [0;9] liegen");
      }
      if(Math.Abs(value) > 31)
      {
        throw new ArgumentOutOfRangeException("value muss im Intervall [-31;31] liegen");
      }
      val = /* hier das Statement für den Setter */;
    }
  }
}

public class Program {
  public static void Main() {
    MultiValue31 values = new MultiValue31();
    values[0] = 0;
    values[1] = 1;
    values[2] = 31;
    values[3] = -31;
    values[4] = 16;
    values[5] = -16;
    values[6] = 8;
    values[7] = -8;
    values[8] = 4;
    values[9] = 2;
  
    for(int i = 0; i < 10; i++)
    {
      Console.WriteLine(values[i]);
    }
  }
}
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von MarsStein am .
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Hi,

ich liebe Bit-Spielereien ;)


      return (sbyte)(((val >> (idx * 6)) & 63) - 32);


      val = (val & ~(63L << (idx*6))) | ((value + 32L) << (idx*6));

Der eingebaute UnitTest sagt bei mir zumindest, dass es korrekt sei, daher fang ich schonmal an eine neue Aufgabe auszugrübeln... :-)

beste Grüße
zommi
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3430
Herkunft: Trier -> München

beantworten | zitieren | melden

Hallo Zommi,

perfekt, genau so war's gedacht

Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Na denn,

mal wieder was algorithmisches:
Gegeben sind 1000 Zahlen. (siehe Anhang)
Was ist die [B]größte[/B] Zahl aus dem Intervall [1 ; 10.000.000], die sich [B]nicht[/B] als Summe von irgendeiner Teilmenge dieser Zahlen bilden lässt?

Die Zahlen sind übrigens frisch von random.org generiert ;)

Kleines Referenzbeispiel:
Gegeben: 2, 2, 3, 5, 7
Interval: [1; 10]
Lösung: 6 (1 und 6 lassen sich nicht darstellen)

Die Fragestellung schreibt hier keine Programmiersprache vor, oder ob iher überhaupt selbst was coden müsst. Die Lösung irgendwie zu bekommen, ist schon tricky genug! (glaube ich)
Aber am schönsten is natürlich ein kleines C#-Programm, dass diese Frage (und ähnliche) beantwortet.

beste Grüße
zommi
Attachments
private Nachricht | Beiträge des Benutzers
sth_Weird
myCSharp.de - Member



Dabei seit:
Beiträge: 472
Herkunft: BaWü

beantworten | zitieren | melden

und jede Zahl die vorkommt darf maximal 1* verwendet werden (also es sei denn die Zahl käme in der Liste zweimal vor dann dürfte sie zweimal verwendet werden)?

gruß
sth_Weird
~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+
Fluchen ist die einzige Sprache, die jeder Programmierer perfekt beherrscht
* * *
Linux is for free...if your time is worth nothing
~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Zitat
und jede Zahl die vorkommt darf maximal 1* verwendet werden (also es sei denn die Zahl käme in der Liste zweimal vor dann dürfte sie zweimal verwendet werden)?
Ja, exakt.
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

hm... das ist ein np-hartes problem und die eingabemenge (n) ist gigantisch... die subsum ergebnissmenge (m) ist auch gigantisch. die gängigen algorithmen, die das in relativ annehmbarer zeit schaffen würden, würden n*m*4 bytes speicher nur für die lookup-tabelle verfressen... was so ziemlich jede .net anwendung überlastet. nicht jeder hat ~37 GB ram.


könnte man daher die aufgabenstellung auf ein realistisches maß herunterschrauben?


ps: für alle die es noch nciht wissen --> http://de.wikipedia.org/wiki/Untermengensumme
sth_Weird
myCSharp.de - Member



Dabei seit:
Beiträge: 472
Herkunft: BaWü

beantworten | zitieren | melden

Hmm, weil du geschrieben hast von wegen Programmiersprache nicht vorgegeben und evtl garnichts schreiben müssen...

mein Ansatz wäre eine Wahrheitstabelle zu erstellen, wobei jede Spalte den Index auf die Zahlenliste darstellt. Also bei 3 Zahlen sähe die so aus:
000
001
010
011
100
101
110
111
und dann könnte man die zeilenweise durchlaufen und die Summe der Zahlen bilden, bei denen eine 1 steht, und das dann in einen Hash schreiben.
Danach müsste man nur noch von der Maximalzahl rückwärts runterzählen bis man eine Zahl findet, die nicht im Hash steht.

Bei 1000 Zahlen ist das tatsächlich ein Problem, denn die Tabelle hätte ja 2^1000 Zeilen.
Der nächste Ansatz ist, die 0en und 1en statt in Zahlenform in ein String-Array zu packen (also 1000 Strings im Array, jeder 2^1000 lang).
Und dann quasi durch die chars gehen und die Zahlen derart erzeugen.
Leider war die Pause zu kurz zum implementieren, musst dich also, wenn du auf ausprogrammierten Code bestehst, noch ein bissl gedulden, jetzt gehts zurück an die Arbeit

gruß
sth_Weird
~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+
Fluchen ist die einzige Sprache, die jeder Programmierer perfekt beherrscht
* * *
Linux is for free...if your time is worth nothing
~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

@ Jack:
sehr gut recherchiert! SubSetSum ist das richtige Stichwort. (Wobei "Inverse SubSetSum" evtl. passender wäre)

@ sth_Weird:
Das "Durchprobieren" ist als naiver Ansatz leider viel zu langsam. Die exponentielle Laufzeit macht dir da einen derben Strich durch die Rechnung.

Die Eingabe/Ergebnismengen wurden extra so gewählt, dass der naive Ansatz nicht zu unserer Lebzeit fertig wird :-)

Auch der von Jack zitierte gängige Algorithmus mit seiner m*n-Lookuptable schlägt hier fehl. Wie Jack korrekt bemerkt, würde dieser Gigabytes an Speicher benötigen.

Dennoch ist die Idee mit einer Lookuptable sehr gut und zielführend!
Nur muss man die Unterschiede zum Standard-SubSetSum finden. Dort ist nämlich auch die genaue Summation relevant (welche Teilmenge).
Hier ist das völlig egal! Nutzt es aus!

Daher:
Zitat von JAck30lena
könnte man daher die aufgabenstellung auf ein realistisches maß herunterschrauben?
Nein. Ziel soll es gerade sein, einen Algo zu suchen, der trotz der Komplexität dieses Problem knackt! (Und das ist schaffbar mit ein paar MB Ram und in ~ 10 Sekunden)

beste Grüße
zommi
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

Zitat
Dort ist nämlich auch die genaue Summation relevant (welche Teilmenge).
Hier ist das völlig egal!

aber es heißt doch:
Zitat
und jede Zahl die vorkommt darf maximal 1* verwendet werden

und ob ich mir jetzt die verwendete zahl oder den index der verwendeten zahl merke ist egal. daher ist die gennaue summation schon relevant? oder habe ich da was falsch verstanden?
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Die genaue Summation ist nicht relevant.
Man muss beim Bilden einer Summe natürlich aufpassen, dass jede Zahl nur höchstens einmal betrachtet wird.

Es reicht aus zu wissen, ob eine gewisse Summe aus gewissen Zahlen erreichbar ist oder nicht. Hierfür interessiert es niemanden, welche Zahlen genau verwendet wurden.

PS: Ich werd dann heute abend/morgen früh noch n Tipp in die Runde werfen. Aber ich will euch ja auch nicht das Grübeln vermiesen ;-)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von zommi am .
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

harter brocken... ich hab eine lösung, die schon perfomanter ist als der naive weg aber dennoch ~10^36 iterationen benötigt und daher nicht in einer annehmbarer zeit fertig ist.... :-(
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Stimmt, Billiarden Jahre wollen wir hier nicht warten
Skizzier doch kurz deine bisherige Idee. Das hilft dann auch anderen, die vielleicht mit ihren Ideen wieder dir helfen ?!

Und 10^36 is schonmal besser als 10^301 (=2^1000) !

beste Grüße
zommi
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

mein code:

           
main...
{
 List<int> input = File.OpenText(Path.Combine(Environment.CurrentDirectory, "random.txt"))
                .ReadToEnd()
                .Split(new[] {Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries)
                .Select(aString => int.Parse(aString))
                .ToList();
            int max = 10000000;
            List<int> selectedIndexList = new List<int>();
            
            SearchMaxSubsetSum(ref max, input, selectedIndexList);

            Console.WriteLine(max);
            Console.ReadLine();
            
  }      

        public static int stackCount = 0;

        public static void SearchMaxSubsetSum(ref int max, List<int> inputValues, List<int> selectedIndexList)
        {
            Console.WriteLine(string.Format("{0,-20} {1}",StackCountString(stackCount),max));
            int preselectedSum = selectedIndexList.Sum(index => inputValues[index]);
            for (int i = 0; i < inputValues.Count; i++)
            {
                int index = i;
                if(selectedIndexList.Any(item => item == index)) continue;

                int currentSelectedSum = preselectedSum + inputValues[i];

                if(currentSelectedSum < max)
                {
                    selectedIndexList.Add(i);
                    stackCount++;
                    SearchMaxSubsetSum(ref max,inputValues,selectedIndexList);
                    //if (selectedIndexList.Sum(selectedIndex => inputValues[selectedIndex]) ≥ max) return;

                    selectedIndexList.Remove(i);
                }
                else if(currentSelectedSum == max)
                {
                    max--;
                    stackCount--;
                    Console.WriteLine(max);
                    return;
                }
            }
            stackCount--;
            
        }

        public static string StackCountString(int einrücker)
        {
            if (einrücker ≤ 0) einrücker = 1;
            return string.Format("{0," + einrücker + "}", 0);
        }

oh und ich habe mich geirrt, was die laufzeit angeht, da ich ja 10^36 iterationen bruache um eine zahl zu überprüfen aber ich muss ja alle 10.000.000 zahlen überprüfen (worst case) also wären das dann 10^43 und das auch nur deswegen, weil die input zahlen im schnitt so groß sind, das nciht mehr als 12 zahlen summiert werden müssen, um herauszufinden ,das man eigendlisch schon drüber ist...
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Ich würde mal dezent 400251 in die Runde werfen.
Falls es richtig sein sollte, gibt's auch Code ;)

Gruß,
dN!3L
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
inflames2k
myCSharp.de - Experte

Avatar #AARsmmPEUMee0tQa2JoB.png


Dabei seit:
Beiträge: 2360

beantworten | zitieren | melden

Gemäß dem Fall der Wert ist richtig, würde mich schon interessieren wie du es ermittelt hast.
Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager | Spielkartenbibliothek
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

400251 lässt sich zwar nach meinen Berechnungen ebenfalls nicht als Summe dieser Zahlen darstellen, ist jedoch nicht die größte (Aus dem Intervall bis 10 Mio) !

Insofern: Leider falsch ! (sofern ich keinen Fehler gemacht hab )

Aber dass es geraten war, glaube ich mal nicht, da nur 6,18147% aller Zahlen aus [1; 10Mio] nicht als Summe dieser Zahlen darstellbar sind.

Aber die Zahl ist schonmal in einer "interessanten" Größenordnung, sodass du deinen Ansatz zumindest posten solltest.

beste Grüße
zommi
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von zommi am .
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von zommi
ist jedoch nicht die größte (Aus dem Intervall bis 10 Mio)
Ich habe ab 10 Mio abwärts prüfen lassen. 400251 war bei mir die erste, die nicht gepasst hat.
EDIT: Verdammt, das Caching/die Lookup-Tabelle klappt nicht ganz. Ohne werden mehr Zahlen als nicht darstellbar erkannt. Grml...
Zitat von zommi
Aber die Zahl ist schonmal in einer "interessanten" Größenordnung, sodass du deinen Ansatz zumindest posten solltest
Ich muss nochmal drübergucken. Im Moment wird noch der Spezialfall behandelt, dass deine Testmenge keine doppelten Werte enthält. Mal sehen, ob ich das noch rausbekomme und vll. noch eine größere Zahl finde. Ich werd mich dann heute Abend nochmal genauer mit beschäftigen. :)

Neuer Vorschlag: 699188

Beste Grüße,
dN!3L
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Zitat von dN!3L
Neuer Vorschlag: 699188
Ne, noch größer.
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Zitat von Programmausgabe
Durchgang: 1000 / 1000
Suche Lösung....
Lösung:956176
Dauer: 84,95 sec.
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von Floste
Lösung: 956176
Also meine Testfunktion sagt mir, dass 956176 zerlegbar ist. Ich gucke mal, ob ich die Summanden rausbekomme. EDIT: War wohl irgendwie eine Zahl falsch eingelesen.
956176 kann ich bestätigen.

Hier mein Code dazu:


public static void DoWork()
{
	List<int> test = Calculate(new int[]{ 2,2,3,5,7 },10).ToList();
	Debug.Assert(test.Count==2 && test.Contains(1) && test.Contains(6));
	
	var values = File.ReadAllLines("random.org.txt").Select(line => Int32.Parse(line));
	int result = Calculate(values,10000000).Last();

	Debug.Assert(!CanSubstitute(values.ToList(),result));
}

private static IEnumerable<int> Calculate(IEnumerable<int> values,int limit)
{
	bool[] map = new bool[limit*2];
	foreach (int value in values)
	{
		for (int i=limit;i>0;i--)
			if (map[i])
				map[i+value] = true;
		map[value] = true;
	}
	return Enumerable.Range(1,limit).Where(i => !map[i]);
}

private static bool CanSubstitute(IList<int> list,int value)
{
	return CanSubstitute(list.OrderByDescending(v => v).ToList(),0,value);
}

private static bool CanSubstitute(IList<int> list,int startIndex,int targetValue)
{
	if (startIndex≥list.Count || targetValue≤0)
		return false;
	else if (list[startIndex]==targetValue)
		return true;
	else if (CanSubstitute(list,startIndex+1,targetValue-list[startIndex]))
		return true;
	else if (CanSubstitute(list,startIndex+1,targetValue))
		return true;
	else
		return false;
}

Im Prinzip funktioniert es ähnlich dem Sieb des Eratosthenes. Es werden alle Zahlen im Suchbereich markiert, die irgendwie über eine Summe erreichbar sind.

Die CanSubstitute-Methode habe ich noch als Test mit drin gelassen. Bevor mir vorhin beim Essen die rettende Idee gekommen ist, hatte ich mit ihr einfach BruteForce gemacht.

Gruß,
dN!3L
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Meine lösung sah so aus:

        static void Main(string[] args)
        {
            Stopwatch sw = Stopwatch.StartNew();
            const int max=10000000;
            int[] numbers = File.ReadAllLines("random.org.txt").Select((line) => int.Parse(line)).ToArray();
            //int[] numbers = { 2, 2, 3, 5, 7 };
            bool[] reached = new bool[max+1];
            reached[0] = true;
            for (int i = 0; i < numbers.Length; i++)
            {
                Console.Write("\rDurchgang: "+(i+1)+" / " +numbers.Length);
                int number = numbers[i];
                for (int i2 = max-number; i2≥0; i2--)
                {
                    reached[i2+number]|=reached[i2];
                }
            }
            Console.WriteLine();
            Console.WriteLine("Suche Lösung....");
            for (int i = max; i ≥ 0; i--)
            {
                if (!reached[i])
                {
                    Console.WriteLine("Lösung:" + i);
                    break;
                }
            }
            sw.Stop();
            Console.WriteLine("Dauer: "+(sw.ElapsedTicks/(double)Stopwatch.Frequency).ToString("0#.00")+" sec.");
            Console.ReadLine();
        }

Mich würde mal interessieren, wie lange dein code braucht.
Mein code hate ein laufzeitverhalten von ca. suchbereichGröße*anzahlZahlen

irgendwie sind unsere einlesemethoden zeimlich identisch. 8o
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von Floste
Mich würde mal interessieren, wie lange dein code braucht
Deine dürfte weniger Schleifendurchläufe machen, als meiner, da du Abbruchbedingung geschickter gewählt hast.
Teste doch einfach mal den Laufzeitunterschied. Wenn ich dir sage, mein Code braucht 1min13sec ist dir ja auch nicht viel geholfen, da wir ja unterschiedliche Maschinen haben.
Aber an die "unter 15sec" von Zommi dürften wir noch weit weg sein...
Zitat von Floste
irgendwie sind unsere einlesemethoden zeimlich identisch.
Hehe. Pattern...

Gruß,
dN!3L
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

Zitat
Aber an die "unter 15sec" von Zommi dürften wir noch weit weg sein...

vielleicht hat zommy einfach nur eine monstermaschine :-) oder nutzt parallel programming. so wie ich das sehe ließe sich der sieb gut parallelisieren.
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Soo, vom Halbfinalspiel zum Programmierspiel :-)

956176 ist korrekt !!!! :-)
Flotse hat den Pokal, auch wenn dN!3L dicht dran war. (könnt ja untereinander ausmachen, wer nächste Aufgabe stellt)

@Monstermaschine...
Flotses Code (84,95 sec) läuft bei mir in 7 sec durch . (intel Q9300)

Mein Referenz-Code sieht auch aus wie euer:

public static void Main() {
	int[] array = File.ReadAllLines("random.org.txt").Select(s => Int32.Parse(s)).ToArray();
	Stopwatch sw = Stopwatch.StartNew();	
	
	Console.WriteLine("MaxSum: {0}", MaxNonReachableSum(array, 10000000));
	
	sw.Stop();
	Console.WriteLine("Time: {0} ms", sw.ElapsedMilliseconds);	
}
	
public static int MaxNonReachableSum(int[] values, int maximumSum)
{
	bool[] reachable = new bool[maximumSum+1];
	reachable[0] = true;
	
	foreach(int value in values)
		for(int subSum = maximumSum; subSum ≥ value; subSum--)
			reachable[subSum] |= reachable[subSum - value];
							
	return Array.LastIndexOf(reachable, false);
}

Und auch hier wieder dieselbe Einleseroutine ^^

beste Grüße
zommi
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Ich habe mal in meiner Version die Schleife mal parallelisiert (Parallel.ForEach). Macht auf meinem System (2 Kerne) mit meinem for-Schleifenkopf ~38sec, mit flostes for-Schleifenkopf ~14sec.
Auf nem 8-Kern-Server bekomme ich es runter auf ~1,5sec. (Für die 16 Kerne müsste ich erst auf den Wartungsslot warten :P).

Gruß,
dN!3L
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Zitat
Macht auf meinem System (2 Kerne) mit meinem for-Schleifenkopf ~38sec,

Ich habe meinen code mal etwas optimiert und er läuft jetzt bei mir AUF EINEM KERN in 2,18 sec durch und verbraucht nunoch 1/8 des speichers:


Stopwatch sw = Stopwatch.StartNew();
            const int max=10000000;
            int[] numbers = File.ReadAllLines("random.org.txt").Select((line) => int.Parse(line)).ToArray();

            byte[] reached = new byte[divUp(max,8)+8];//aufrunden und 8 bytes sicherheit
            fixed (byte* preadced = &reached[0])
            {
                preadced[0] = 1;
                for (int i = 0; i < numbers.Length; i++)
                {
                    Console.Write("\rDurchgang: " + (i + 1) + " / " + numbers.Length);
                    int number = numbers[i];
                    int numberBytes=number/32;
                    int bitshift=number%32;
                    for (int i2 = divUp(max-number,32); i2 ≥ 0; i2--)
                    {
                        uint src=*((uint*)(preadced+(i2*4)));
                        *((ulong*)(preadced + (4*(i2 + numberBytes)) )) |= (((ulong)src) << bitshift);
                    }
                }
            }
            Console.WriteLine();
            Console.WriteLine("Suche Lösung....");
            for (int i = max; i ≥ 0; i--)
            {
                int numberBytes = i / 8;
                int bitshift = i % 8;
                if ((reached[numberBytes]&(1<<bitshift))==0)
                {
                    Console.WriteLine("Lösung:" + i);
                    break;
                }
            }
            sw.Stop();
            Console.WriteLine("Dauer: "+(sw.ElapsedTicks/(double)Stopwatch.Frequency).ToString("0#.00")+" sec.");
            Console.ReadLine();


        private static int divUp(int i, int d)
        {
            if (i % d == 0) return i / d;
            else return i / d + 1;
        }
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Jaja, dass am Ende jemand das Bit-Array auspacken würde, das hatte ich schon befürchtet

beste Grüße
zommi


In C/C++ ließe sich diese schöne innere Schleife noch perfekt mittels SSE beschleunigen. Da wird dann nicht mehr 1 oder 32 Bit verarbeitet, sondern gleich 128 (bzw 64, weil man ja nur die hälfte hat)...mhh...wenn jemand nix zu tun hat? Da wär nochmal Faktor 2 zu holen ;-)


Ist schon herrlich, wie man mit n paar Zeilen Code (die sogar einfacher und kürzer als BruteForce sind - den BitQuatsch mal außen vor gelassen ;-)) die Laufzeit einer Problemlösung von grob 10^280 Jahren auf 1,5 Sekunden runterbrechen kann Das find ich echt faszinierend.
Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von zommi am .
private Nachricht | Beiträge des Benutzers
fielding
myCSharp.de - Member



Dabei seit:
Beiträge: 62

beantworten | zitieren | melden

die aufgabe war wirklich interessant, kann vllt einer noch für nicht-mathematiker erklären was da passiert? aus
Zitat
Im Prinzip funktioniert es ähnlich dem Sieb des Eratosthenes. Es werden alle Zahlen im Suchbereich markiert, die irgendwie über eine Summe erreichbar sind.
werd ich nicht schlau. Ich kenn zwar das Sieb des Eratosthenes und verstehs auch, den transfer zu diesem problem bekomme ich aber leider nicht hin. Allgemein würde man sich über 2 oder 3 kommentare in den Lösungen immer freuen ;)
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Beispiel: { 2,2,3,5 } im Bereich [1,10]. Man geht die Zahlen der Reihe nach durch:
  • Mit der 2 kann man die 2 erreichen. (Zwischenergebnis erreichbare Zahlen: 2)
  • Mit der nächsten 2 kann man wieder die 2 erreichen (haben wir schon), und von der vorhandenen 2 aus die 4. (ZE: 2,4)
  • Mit der 3 kann man die 3 erreichen. Und über die vorhandene 2 und 4 die 5 und die 7. (ZE: 2,3,4,5,7).
  • Mit der 5 kann man die 5 erreichen. Und über die vorhandene 2, 3, 4, 5 und 7 die 7 (haben wir schon), die 8, die 9, die 10 und die 12 (liegt aber nicht im Bereich). (ZE: 2,3,4,5,7,8,9,10)
Man kommt also über Summenbildung auf die Zahlen 2, 3, 4, 5, 7, 8, 9 und 10. Die 1 und die 6 können nicht erreicht werden.

Gruß,
dN!3L
private Nachricht | Beiträge des Benutzers