Häufigste Zahl einer Zahlenreihe ermitteln

SeppJ schrieb:

Allgemeines Bashing: Sortieren ist selten ein guter Ansatz für eine Lösung, außer das Problem ist, etwas zu sortieren .

Sortieren ist gar nicht mal so langsam und vor allem verschwendet das keinen Speicher (O(1) statt O(n))

Dagegen lässt sich mein Ansatz leicht anpassen, dass die Elemente nicht kopiert werden müssen.

@Anwendungsbeispiel:

std::vector<int> values = ...
std::pair<int*,size_t> result = most_frequent_element(values.begin(), values.end());
// wenn values.size() == 0, dann ist result.first == NULL
std::cout << *result.first << " kommt " << result.second << " mal vor\n";

HarteWare

SeppJ schrieb:

Klar, man kann ja schon beim Zählen gucken, welches Element das Häufigste ist. Da war ich mit meinem ersten Vorschlag etwas voreilig. So ist es sogar nur O(N*log(M)) (oder bis zu O(N) mit Tabelle). Was in so ziemlich allen Fällen besser sein sollte als die Sortiermethode. Allgemeines Bashing: Sortieren ist selten ein guter Ansatz für eine Lösung, außer das Problem ist, etwas zu sortieren .

Mit einem Vector<int> werte; ? Ich komm nicht drauf wie das gehen sollte. Kannst vielleicht ein paar Zeilen Pseudecode rauslassen oder einen Tipp geben?

mfg
HarteWare

SeppJ

Nun, statt einer map eben eine unordered_map. Oder, wenn man weiß, dass die möglichen Werte überschaubar sind und man daher keine richtige Hashmap braucht, ein vector zum Mitzählen. So drückt man die Zugriffszeit von log(M) auf eine Konstante.

HarteWare

@stell
Die Anwendung ist auf jeden Fall simpler als der Code selbst Ich habs mal abgespeichert falls ich sowas mal wieder benötige. (ernsthaft jetzt, benutze immernoch dieses skip_char<> template von out fürs "Parsen" von .txt Dateien )

Es ging bei mir lediglich um eine Aufgabe aus einem Buch und ich wusste dass die verschachtelte for-Schleife dafür einfach ... ist. Die Aufgaba kam zu einem Zeitpunkt wo ich theoretisch nur vector, diverse Operatoren, Schleifen, If-Abfragen und Datentypen kennen sollte, daher wäre alles andere "geschummelt".

Hätte ich vielleicht auch früher sagen können^^ Aber ich denke das Thema ist soweit abgeschlossen, vielen Dank an alle Mitwirkenden

mfg
HarteWare

knivil

Allgemeines Bashing: Sortieren ist selten ein guter Ansatz für eine Lösung, außer das Problem ist, etwas zu sortieren

Wenn ich die Laufzeit von irgendwas druecken moechte, was nicht schon O(n log n) ist, dann versuche ich es in ein Sortierproblem zu verwandeln. Viele geometrische Algorithmen basieren darauf. Und die Messung Sortierung vs. Hashtabelle moechte ich sehen.

SeppJ

knivil schrieb:

Und die Messung Sortierung vs. Hashtabelle moechte ich sehen.

Ich eigentlich nicht, aber wenn hier der Hashtable nicht um Größenordnungen gewinnt, würde mich das wundern. Vielleicht nicht bei < 100 Zahlen, aber die bessere Laufzeitkomplexität sollte ziemlich schnell gewinnen.

Um mal auf stells Ansatz aufzusetzen: Man kann Kopien der Werte im Vektor auch komplett vermeiden, indem man in der Hashmap Verweise speichert -- also auch die, die in der unordered_map angelegt werden. Es erfordert allerdings einen Kunstgriff -- verzeiht die wenig sprechende Nomenklatur:

#include <cstddef>
#include <iostream>
#include <unordered_map>
#include <vector>

template<typename T>
class hashref {
public:
  hashref(std::size_t index,
          std::vector<T> const &container)
    : index_(index),
      container_(container) {
  }

  hashref const &operator=(hashref const &other) {
    index_ = other.index_;
    return *this;
  }

  bool operator==(hashref const &other) const {
    return container_[index_] == other.container_[other.index_];
  }

  std::size_t hash () const { return std::hash<T>()(container_[index_]); }
  std::size_t index() const { return index_; }

private:
  std::size_t           index_;
  std::vector<T> const &container_;
};

template<typename T>
struct refhash {
  std::size_t operator()(hashref<T> const &val) const {
    return val.hash();
  }
};

template<typename T>
std::size_t index_of_most_frequent_value(std::vector<T> const &vec) {
  std::unordered_map<hashref<T>, unsigned, refhash<T>> counters;
  hashref<T> result(0, vec);
  unsigned   result_count = 0;

  for(std::size_t i = 0; i < vec.size(); ++i) {
    if(++counters[hashref<T>(i, vec)] > result_count) {
      result = hashref<T>(i, vec);
      ++result_count;
    }
  }

  return result.index();
}

int main() {
  std::vector<int> data { 3, 3, 4, 1, 1, 1, 2, 3, 4, 3, 2, 2, 1, 0, 1, 3, 3, 3 };

  std::cout << index_of_most_frequent_value(data) << '\n';
  std::cout << data[index_of_most_frequent_value(data)] << '\n';
}

Das ist bei einem std::vector<int> nicht so richtig spannend, aber wenn mal komplexere Datentypen darinstecken (ich denke da in Richtung bigints) mag das was bringen. Oder wenn es std::vector<std::unique_ptr<foo> > ist oder so.

knivil schrieb:

Und die Messung Sortierung vs. Hashtabelle moechte ich sehen.

Wird gemacht. Aber ich kann dir jetzt schon sagen, dass die Hashtable bei immer größeren Datenmengen immer besser abschneiden wird. Jedenfalls, sofern die Daten aus einer vertrauenswürdigen Quelle stammen.

Mir fällt beim Benchen mit Zufallszahlen grad auf, dass der Hashtable-Ansatz nur dann sinnvoll mit großen Datenmengen funktionieren kann, wenn die Wertemenge relativ klein ist (also die Ints im Vektor nur eine begrenzte Menge verschiedener Int-Werte annehmen können). Ist das hier der Fall, und ggf. auf welchen Bereich sind die Werte beschränkt?

HarteWare schrieb:

Es ging bei mir lediglich um eine Aufgabe aus einem Buch und ich wusste dass die verschachtelte for-Schleife dafür einfach ... ist. Die Aufgaba kam zu einem Zeitpunkt wo ich theoretisch nur vector, diverse Operatoren, Schleifen, If-Abfragen und Datentypen kennen sollte, daher wäre alles andere "geschummelt".

Hätte ich vielleicht auch früher sagen können^^ Aber ich denke das Thema ist soweit abgeschlossen, vielen Dank an alle Mitwirkenden

seldon schrieb:

Um mal auf stells Ansatz aufzusetzen: Man kann Kopien der Werte im Vektor auch komplett vermeiden, indem man in der Hashmap Verweise speichert -- also auch die, die in der unordered_map angelegt werden. Es erfordert allerdings einen Kunstgriff -- verzeiht die wenig sprechende Nomenklatur:

Das geht sogar mit meiner ursprünglichen Funktion.

Man braucht nur zwei Helferklasssen:

template<typename T, typename H=std::hash<T> >
struct refhash : H {
  std::size_t operator()(std::reference_wrapper<T> const &val) const {
    return static_cast<H const&>(*this)(val);
  }
};
template <typename T, typename E=std::equal_to<T> >
struct refequal : E {
  std::size_t operator()(std::reference_wrapper<T> const &lhs,
                         std::reference_wrapper<T> const &rhs) const {
    return static_cast<E const&>(*this)(lhs.get(), rhs.get());
  }
};

Und schon geht es ohne meine Funktion auch nur anzufassen:

most_frequent_element<std::vector<int>::iterator,
                      std::unordered_map<std::reference_wrapper<int>,
                                         std::size_t,
                                         refhash<int>,
                                         refequal<int> > >(...);

In meiner Messung (häufigstes Wort aus http://www.gutenberg.org/files/2600/2600.txt ) ist die Hashmap 6x schneller als das Sortieren, da sind die Daten aber auch wie geschaffen dafür.