Angepinnt [Sammelthread] Knobel-Aufgaben, knifflige Algorithmen, elegante Lösungen

    • VB.NET

    Es gibt 178 Antworten in diesem Thema. Der letzte Beitrag () ist von Thunderbolt.

      VB.NET-Quellcode

      1. ''' <summary>
      2. ''' Gibt die Summe aller Zeilen der Dateien in dem angegebenen Verzeichnis zurück.
      3. ''' </summary>
      4. ''' <remarks>wirft natürlich haufenweise Exceptions, wenn ungeeignete Directories oder Files vorliegen</remarks>
      5. Public Shared Function countLines(path As String, Optional searchPattern As String = "*", Optional searchOption As SearchOption = IO.SearchOption.TopDirectoryOnly) As Integer
      6. Return Directory.GetFiles(path, searchPattern, searchOption).SelectMany(AddressOf File.ReadAllLines).Count()
      7. End Function

      Statt ReadAllLines() sollte man besser ReadLines() verwenden.
      Das array, das man aus ReadAllLines() bekommt scheint nicht sofort freigegeben zu werden.
      Zumindest belegt die Anwendung weiterhin ziemlich viel Speicher.
      Wenn man dann noch alle Zeilen in ein Ding stopft (wie beim EDR), dann kommt es zur OutOfMemory Exception (bei großen Dateien).
      Auch nach dem terminieren der countLines Methode scheint sich der GC erst mal nicht um das Array zu kümmern. GC fail. Erst wenn der Speicher knappt wird, läuft der GC an.
      Bei ReadLines() werden alle vorherigen Zeilen sofort weggeschmissen. Bei einem Test mit einer Datei von mehreren 100 mb war ReadLines() auch noch ein gutes Stück schneller.

      Mein Vorschlag wäre gewesen:

      VB.NET-Quellcode

      1. Return New DirectoryInfo(path).EnumerateFileSystemInfos(searchPattern, searchOption).Sum((Function(fileInfo) File.ReadAllLines(fileInfo.FullName).Count()))

      oder

      VB.NET-Quellcode

      1. Return New DirectoryInfo(path).EnumerateFileSystemInfos(searchPattern, searchOption).Select(Function(fileInfo1) File.ReadLines(fileInfo1.FullName).Count()).Sum()


      Zum Thema Exceptions: Die Überprüfung, ob die Parameter korrekt sind, gehen natürlich nicht in eine Zeile.

      [OT](guck - selbst ganz einfache Knobeleien sind lohnend: File.ReadLines kannte ich noch garnet - was ich immer sage: immer feste ObjectBrowser gugge - und jetzt habichmich selbst erwischt ;))[/OT]

      markus.obi schrieb:

      Thema Exceptions...
      Mehr Sorgen machen mir Exceptions aufgrund fehlender ZugriffsRechte, und was passiert, wenn .ReadLines an eine Binär-Datei gerät? 8|

      ReadLines kannte ich auch nicht. Btw. Binärdateien funktionieren auch, auch wenn es sich dann nicht unbedingt um klassisch definierte Zeilen, sondern Zeilenumbrüche handelt. Bei ReadAllLines würde ich zu Length statt Count greifen, da Count auf IEnumerable(Of T) definiert wurde und somit nicht in O(1), sondern O(n) liegt.

      Gruß
      ~blaze~

      Mein Fehler. Ich meinte natürlich ReadLines. da sollte das Count ja egal sein, weil die Auflistung eh nur einmal durchlaufen wird.
      @EDR bei ReadLines hat z.B. den Vorteil, dass aufgrund der faulen Auswertung die Zeilen zum spät möglichsten Zeitpunkt gelesen werden.

      Ich hoffe, ich platze hier nicht gerade in eine Diskussion, aber ich hätte hier noch was zum knobeln:

      Es geht darum, Speichergrössen in den verschiedenen Formaten vernünftig darzustellen. Die Idee kommt von EDR, als er die grosse und umständliche Lösung meinerseits sah.

      Grüsse

      Higlav

      Nafets hatte eigentlich schon den richtigen Lösungsweg gepostet, hier hasts dus nochmal ausgearbeitet:

      C-Quellcode

      1. public static double ConvertMemoryUnit(double value, MemoryUnit inputUnit, MemoryUnit outputUnit)
      2. {
      3. double bitValue = value * (long)inputUnit;
      4. return bitValue / (long)outputUnit;
      5. }
      7. public enum MemoryUnit : long
      8. {
      9. Bit = 0x1,
      10. KiloBit = 1000 * Bit,
      11. KibiBit = 0x400 * Bit,
      12. MegaBit = 1000 * KiloBit,
      13. MebiBit = 0x400 * KibiBit,
      14. GigaBit = 1000 * MegaBit,
      15. GibiBit = 0x400 * MebiBit,
      16. TeraBit = 1000 * GigaBit,
      17. TebiBit = 0x400 * GibiBit,
      18. Byte = 0x8 * Bit,
      19. KiloByte = 1000 * Byte,
      20. KibiByte = 0x400 * Byte,
      21. MegaByte = 1000 * KiloByte,
      22. MebiByte = 0x400 * KibiByte,
      23. GigaByte = 1000 * MegaByte,
      24. GibiByte = 0x400 * MebiByte,
      25. TeraByte = 1000 * GigaByte,
      26. TebiByte = 0x400 * GibiByte,
      27. }

      GruppierungsFunktion

      Gesucht wird eine Gruppierungs-Funktion, der man ein IEnumerable(Of T) hinschmeißt + eine Auflistung von Integern, und zurück bekommt man ein IEnumerable(Of T()), also eine Auflistung kleiner Arrays. Und jedes Array ist so groß, wie durch die Integer-AuflistungEnumeration angegeben.
      Hier die Signatur:

      VB.NET-Quellcode

      1. <Extension()> _
      2. Public Function Group(Of T)(lst As IEnumerable(Of T), groupSizes As IEnumerable(Of Integer)) As IEnumerable(Of T())
      3. Return New Grouped(Of T)(lst, groupSizes)
      4. End Function
      Eine Weitere Überladung würde eine Gruppen-Auflistung mit Arrays gleicher Größe bewirken:

      VB.NET-Quellcode

      1. <Extension()> _
      2. Public Function Group(Of T)(lst As IEnumerable(Of T), groupSize As Integer) As IEnumerable(Of T())
      3. Return lst.Group(Enumerable.Repeat(groupSize, Integer.MaxValue))
      4. End Function
      zu sehen? aus der einzelnen GroupSize wird eine unendlich lange GroupSize-Enumeration gebastelt - alle gleich groß.

      Nutzbar wäre son Ding etwa, um zB einen String an definierten Stellen aufzuteilen, und so testet auch die Testanwendung:

      VB.NET-Quellcode

      1. Imports System.Diagnostics
      3. Public Module modMain
      5. Sub Main(ByVal commands As String())
      6. Dim s = "012345678901234567890123456789"
      7. Dim output As Action(Of IEnumerable(Of Char())) = Sub(grps) Debug.Print(String.Join("-", grps.Select(Function(gp) New String(gp))))
      8. output(s.Group(10))
      9. output(s.Group(9))
      10. output(s.Group({9}))
      11. output(s.Group({10, 10, 9}))
      12. output(s.Group({10, 10, 10}))
      13. output(s.Group({10, 10, 11}))
      14. output(s.Group({10, 10}))
      15. End Sub
      17. End Module
      Ausgabe:

      Quellcode

      1. 0123456789-0123456789-0123456789
      2. 012345678-901234567-890123456-789
      3. 012345678-901234567890123456789
      4. 0123456789-0123456789-012345678-9
      5. 0123456789-0123456789-0123456789
      6. 0123456789-0123456789-0123456789
      7. 0123456789-0123456789-0123456789

      Aber wäre natürlich noch viel breiter nutzbar, denn man könne jedes IEnumerable(Of T) damit segmentieren

      Ich hab das auch schon gelöst, aber in vb2010, und sehr umständlich, und meine Hoffnung ist, ob jmd. dafür eine Iterator-Function schreiben mag, das dürfte nämlich sehr elegant werden.
      Dateien

      Das hier wäre mein Vorschlag:
      Spoiler anzeigen

      C-Quellcode

      1. public static class GroupExtensions
      2. {
      3. private static IEnumerable<T> Take<T>(this IEnumerator<T> source, int count)
      4. {
      5. for (; count > 0; count--)
      6. {
      7. if (source.MoveNext())
      8. yield return source.Current;
      9. else
      10. yield break;
      11. }
      12. }
      14. public static IEnumerable<T[]> Group<T>(this IEnumerable<T> source, IEnumerable<int> groupSizes)
      15. {
      16. if (groupSizes == null)
      17. throw new ArgumentNullException("groupSizes");
      19. using (IEnumerator<T> sourceEnum = source.GetEnumerator())
      20. {
      21. using (IEnumerator<int> groupEnum = groupSizes.GetEnumerator())
      22. {
      23. while (true)
      24. {
      25. if (groupEnum.MoveNext())
      26. {
      27. T[] arr = sourceEnum.Take(groupEnum.Current).ToArray();
      28. if (arr.Length > 0) yield return arr;
      30. if (arr.Length != groupEnum.Current)
      31. yield break;
      32. }
      33. else
      34. {
      35. var lst = new List<T>();
      36. while (sourceEnum.MoveNext())
      37. lst.Add(sourceEnum.Current);
      38. if (lst.Count > 0)
      39. yield return lst.ToArray();
      40. else
      41. yield break;
      42. }
      43. }
      44. }
      45. }
      46. }
      48. public static IEnumerable<T[]> Group<T>(this IEnumerable<T> source, int groupSize)
      49. {
      50. return source.Group(GetGroupSizes(groupSize));
      51. }
      53. private static IEnumerable<int> GetGroupSizes(int groupSize)
      54. {
      55. while (true)
      56. yield return groupSize;
      57. }
      58. }
      Dateien

      • GroupTest.zip

        (32,9 kB, 37 mal heruntergeladen, zuletzt: )

      Mit VS2010 gar net so leicht. Aber kompilieren geht mit msbuild ohne VS.
      Spoiler anzeigen

      VB.NET-Quellcode

      1. <Extension()> Public Iterator Function Group(Of T)(lst As IEnumerable(Of T), groupSizes As IEnumerable(Of Integer)) As IEnumerable(Of T())
      2. Dim iter = lst.GetEnumerator()
      3. For Each groupSize In groupSizes
      4. Dim arr(groupSize - 1) As T
      5. For i = 0 To groupSize - 1
      6. If iter.MoveNext Then
      7. arr(i) = iter.Current
      8. Else
      9. If i <> 0 Then
      10. Array.Resize(arr, i)
      11. Yield arr
      12. End If
      13. Exit Function
      14. End If
      15. Next
      16. Yield arr
      17. Next
      18. Dim rest As New List(Of T)
      19. While iter.MoveNext
      20. rest.Add(iter.Current)
      21. End While
      22. If rest.Count > 0 Then
      23. Yield rest.ToArray
      24. End If
      25. End Function
      27. <Extension()> _
      28. Public Function Group(Of T)(lst As IEnumerable(Of T), groupSize As Integer) As IEnumerable(Of T())
      29. Return lst.Group(Enumerable.Repeat(groupSize, Integer.MaxValue))
      30. End Function


      Falls es jemand interessiert, wie man ohne VS kompiliert, hier der batch code:

      Quellcode

      1. setlocal
      2. SET PATH=%PATH%;C:\Windows\Microsoft.NET\Framework64\v4.0.30319
      3. msbuild projektname.sln /p:Configuration=Release

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „markus.obi“ ()

      vielen Dank!
      Ich hab übrigens in meiner Aufgabenstellung eine Kleinigkeit vergessen: Wird bei den GroupSizes 0 angegeben, so muss natürlich ein leeres Array geyieldet werden.
      Also output(s.Group({10, 0, 9})) muss 0123456789--012345678-90123456789 ausgeben.

      In Artentus' Lösung ist das leicht eingebaut:

      Quellcode

      1. if(arr.Length > 0 || groupEnum.Current == 0) yield return arr;


      Bei deiner For-Schleife (die mir eiglich viel besser gefällt als das immer mit MoveNext()) - achnee! 8o Das ist ja bereits abgedeckt - so wies aussieht! :thumbsup:

      (msbuild mussichma gucken, ob ich das hinkrieg)

      edit: nee - krieg ich nicht hin - muss ich da eine batch schreiben?

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

      Ich hab doch den Batsch Code gepostet. Es muss natürlich Framework 4.5 installiert sein und der angegebene Pfad muss stimmen.

      Bei meiner Lösung brauchst du nur 2 Zeilen entfernen.
      Ich seh grad der geht auch mit GroupSizes 0 einwandfrei.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „markus.obi“ ()

      Finde den Fehler

      Hab mir grad ein kleines Progrämmchen geschrieben, dass die Messdatenmenge reduzieren sollte und bin auf einen unerwarteten Fehler gestoßen.
      Das Programm sah anders aus, aber folgendes Codeschnipsel reicht auch aus:

      VB.NET-Quellcode

      1. Dim fullpath = "blub.xt"
      2. Dim filtered = File.ReadLines(fullpath).Where(Function(line, i) (i < 2) OrElse (i Mod 10) = 0)
      3. File.WriteAllLines(fullpath, filtered)


      Nach einer Weile war mir dann klar wo der Hund begraben liegt.

      Bitte nicht einfach Ausführen/Debuggen, außer ihr kommt gar net drauf.
      Reinkopieren in VS ist natürlich OK.

      Wo liegt der Hund nun begraben?

      Hm.
      ReadLine ist laut intellisense, in der Lage die Zeilen zu lesen.
      Schließt sie aber nicht.

      Damit steht es imKonflikt mit WriteAllLines => Zugriff verweigert...


      Nutze ReadAllLines.

      Würde das was bringen?

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „NGE'o“ ()

      ErfinderDesRades schrieb:

      erst anfängt zu schreiben, und danach zu lesen? Von wegen lazy evaluating?

      So ähnlich, aber das Locken der Datei beginnt schon in Zeile 2. (musste grad selber nochmal überprüfen). Es wird also zuerst der Lesezugriff ausgeführt.
      Lazy evaluating ist genau das richtige Stichwort. Die Zeilen werden zum spätest möglichen Zeitpunkt gelesen.
      Will heißen, dass beim Schreiben der ersten Zeile die übrigen Zeilen noch gar nicht gelesen wurden. Die Datei ist auf jeden Fall spätestens nach dem Lesen der ersten Zeile gelockt.
      Tests haben ergeben, dass die Datei schon nach dem Aufrufen der ReadLines()-Funktion gesperrt ist.

      Die Fehlermeldung ist ein bisschen irritierend, weil von nem anderen Prozess die Rede ist.
      Der Prozess kann nicht auf die Datei "..." zugreifen, da sie von einem anderen Prozess verwendet wird.



      NGE'o schrieb:

      Zugriff verweigert

      Jop, genau. Wird nicht geschlossen.
      Ja, ReadAllLines würde es beheben, genauso wie ein Anhängen von .ToList() an Zeile 2.

      Die Datei muss ja in jedem Fall vorher komplett eingelesen werden.

      Das war mal ein Beispiel, bei dem die Lazy Evaluation ein bisschen zu lazy war.

      Gegeben sei ein Feld int[X,Y], wobei der jeweilige Index für die Anzahl der Elemente in der jeweiligen Dimension steht. Gegeben sei außerdem ein Punkt s(X|Y), der den Start bestimmt.
      Es soll nun eine Funktion geschrieben werden, die ausgehend von dem Startpunkt, alle angrenzenden Flächen (Zahlen) bestimmt, und zu jeder Zahl den nächsten Punkt zurückgibt.
      Die Funktion soll folgende Struktur haben:
      IDictionary<int, Point> GetAdjacentArea(Point start)
      Zudem darf keine Rekursion angewandt werden.

      Beispielfeld:

      Quellcode

      1. int[,] field =
      2. {
      3. { 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      4. { 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      5. { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      6. { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      7. { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 },
      8. { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2 },
      9. { 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      10. { 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      11. { 2, 0, 0, 0, 2, 0, 0, 0, 0, x, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      12. { 2, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      13. { 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 2, 2, 2, 2, 2 },
      14. { 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      15. { 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      16. { 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      17. { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2 },
      18. { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 },
      19. { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 },
      20. { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 },
      21. { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 },
      22. { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 },
      23. { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 }
      24. }

      x(X|Y) sei der Startpunkt. Es gilt field[x] = 0.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „AliveDevil“ ()

      @AliveDevil Ich versteh das nicht so ganz.
      Gegeben sei ein Feld int[X,Y], wobei der Index für die Anzahl der Elemente steht.
      Da sehe ich aber zwei Indices. Und was steht jetzt für welche Elemente?!
      die ausgehend von dem Startpunkt, alle angrenzenden Flächen (Zahlen) bestimmt, und zu jeder Zahl den nächsten Punkt zurückgibt.
      Was bestimmst du als "angrenzende Flächen" Alle, die an die Nullen grenzen und eine andere Zahl haben? Zu welcher Zahl soll jetzt welcher Punkt zurückgegeben werden?