3. Häufigste Zahl einer Zahlenreihe ermitteln

Häufigste Zahl einer Zahlenreihe ermitteln


  • Gibt es eine schnellere Methode um aus einem Vektor von positiven ints die häufigste Zahl zu finden als zwei ineinander verschachtelte for-Schleifen?

    also in etwa so:

    std::vector<int> values;

int most_common = -1;
int max_occurance = 0;
int temp_occurance = 0;

for(std::size_t i = 0; i < values.size(); ++i)
{
    for(std::size_t j = 0; j < values.size(); ++j)
    {
        if(values[i] == values[j])
        {
            ++temp_occurance;
            if(temp_occurance > max_occurance)
                most_common = values[j];
        }
    }
    max_occurance = temp_occurance;
    temp_occurance = 0;
}

    mfg
    HarteWare

    0
  • K

    Sortieren und Laenge der Gruppen zaehlen, Zeit O(n log n) und Platz O(1).

    0
  • Mod

    Einmal durchiterieren, zu jedem Wert die Häufigkeit mitzählen. O(N + N*log(M) + M), wobei M die Anzahl unterschiedlicher Werte ist. Mit einem Hashtable auch bis zu O(N + M). Oder einfach einem vector, wenn die Werte überschaubar sind, dann garantierte O(N + M).

    0

  • Also vielen Dank erstmal, das ist auf jeden Fall schneller. 🙂

    Setzt das einmal durch iterieren und häufigkeit zählen das vorherige sortieren voraus? (wüsste sonst nicht wie das gehen soll und wüsste es gerne)

    Dann würd mans also so machen:

    std::vector<int> values;

int temp_max = 0, max = 0, highest = -1;

if(values.size() == 1) highest = values[0];
else if(values.size() < 1) {}
else
{
std::sort(values.begin(), values.end());
for(std::size_t i = 1; i < values.size(); ++i)
{
    if(values[i] == values[i-1])
    {
        ++temp_max;
        if(temp_max > max)
            highest = values[i];
            max = temp_max;
    }
    else        
        temp_max = 0;
}
}//else

    mfg
    HarteWare

    P.S.: Soweit ich weiß, geht das Beiträge löschen aus bestimmten Gründen nicht (zumindest nicht für den normal-regisitrierten).

    0
  • K

    Du koenntest einfach dazuschreiben, auf wen du dich beziehst ... Auch funktioniert dein Code nicht fuer Mengen mit nur einem Element.

    0

  • knivil schrieb:

    Du koenntest einfach dazuschreiben, auf wen du dich beziehst ... Auch funktioniert dein Code nicht fuer Mengen mit nur einem Element.

    Ich habe in diesem Fall jeden gemeint, der sich angesprochen fühlt. Das wäre jeder, der, entweder geantwortet hat, oder der die Lösung zu meiner Frage kennt.
    An wen das P.S. war, denke ich ist auch recht klar.

    @knivil: Danke für den Hinweis, werde es in Betracht ziehen. 👍 (etwas "gehackt", aber es erfüllt seinen Zweck)

    mfg
    HarteWare

    0
  • ?
     

    template <typename I, typename Map=std::unordered_map<typename std::iterator_traits<I>::value_type, std::size_t> >
std::pair<typename std::iterator_traits<I>::pointer, std::size_t>
most_frequent_element(I from, I to)
{
  typename std::iterator_traits<I>::pointer best = 0;
  std::size_t cnt = 0;
  for (Map m; from != to; ++from)
    if (++m[*from] > cnt) {
      ++cnt;
      best = &*from;
    }
  return std::make_pair(best, cnt);
}
    0

  • stell schrieb:

    template <typename I, typename Map=std::unordered_map<typename std::iterator_traits<I>::value_type, std::size_t> >
std::pair<typename std::iterator_traits<I>::pointer, std::size_t>
most_frequent_element(I from, I to)
{
  typename std::iterator_traits<I>::pointer best = 0;
  std::size_t cnt = 0;
  for (Map m; from != to; ++from)
    if (++m[*from] > cnt) {
      ++cnt;
      best = &*from;
    }
  return std::make_pair(best, cnt);
}

    Hui, da hab ich was zum analysieren 😃
    Hast mich auch auf ein paar neue Sachen wie std::pair aufmerksam gemacht, mal gucken was dat alles is...

    bei sowas ist es, vorallem für novizen wie mich, immer ganz nett wenn noch ein kurzes Anwendungsbeispiel dabei ist. Ich wüsste jetzt auf anhieb z.B. nicht, wie ich dieses Template benutzen sollte

    Ich danke für die Antwort
    mfg
    HarteWare

    0
  • Mod

    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 🙂 .

    0
  • ?

    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";
    0

  • 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

    0
  • Mod

    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.

    0

  • @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

    0
  • K

    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. 🙂

    0
  • Mod

    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.

    0
  • ?

    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.

    0
  • ?

    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?

    0
  • ?

    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 👍

    0
  • ?

    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.

    0
Anmelden zum Antworten