Sortieren array von ganzen zahlen lexikographisch C++

Zu leisten, die benutzerdefinierte Sortierreihenfolge, die Sie bieten kann, einen Komparator zu std::sort. In diesem Fall, es wird etwas komplexer, mit Logarithmen zu inspizieren einzelnen Ziffern der Zahl in der Basis 10.

Hier ist ein Beispiel — Kommentare inline beschreiben, was Los ist.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cassert>

int main() {
    int input[] { 100, 21, 22, 99, 1, 927, -50, -24, -160 };

    /**
     * Sorts the array lexicographically.
     * 
     * The trick is that we have to compare digits left-to-right
     * (considering typical Latin decimal notation) and that each of
     * two numbers to compare may have a different number of digits.
     * 
     * This is very efficient in storage space, but inefficient in
     * execution time; an approach that pre-visits each element and
     * stores a translated representation will at least double your
     * storage requirements (possibly a problem with large inputs)
     * but require only a single translation of each element.
     */
    std::sort(
        std::begin(input),
        std::end(input),
        [](int lhs, int rhs) -> bool {
            //Returns true if lhs < rhs
            //Returns false otherwise
            const auto BASE      = 10;
            const bool LHS_FIRST = true;
            const bool RHS_FIRST = false;
            const bool EQUAL     = false;


            //There's no point in doing anything at all
            //if both inputs are the same; strict-weak
            //ordering requires that we return `false`
            //in this case.
            if (lhs == rhs) {
                return EQUAL;
            }

            //Compensate for sign
            if (lhs < 0 && rhs < 0) {
                //When both are negative, sign on its own yields
                //no clear ordering between the two arguments.
                //
                //Remove the sign and continue as for positive
                //numbers.
                lhs *= -1;
                rhs *= -1;
            }
            else if (lhs < 0) {
                //When the LHS is negative but the RHS is not,
                //consider the LHS "first" always as we wish to
                //prioritise the leading '-'.
                return LHS_FIRST;
            }
            else if (rhs < 0) {
                //When the RHS is negative but the LHS is not,
                //consider the RHS "first" always as we wish to
                //prioritise the leading '-'.
                return RHS_FIRST;
            }

            //Counting the number of digits in both the LHS and RHS
            //arguments is *almost* trivial.
            const auto lhs_digits = (
                lhs == 0
                ? 1
                : std::ceil(std::log(lhs+1)/std::log(BASE))
            );

            const auto rhs_digits = (
                rhs == 0
                ? 1
                : std::ceil(std::log(rhs+1)/std::log(BASE))
            );

            //Now we loop through the positions, left-to-right,
            //calculating the digit at these positions for each
            //input, and comparing them numerically. The
            //lexicographic nature of the sorting comes from the
            //fact that we are doing this per-digit comparison
            //rather than considering the input value as a whole.
            const auto max_pos = std::max(lhs_digits, rhs_digits);
            for (auto pos = 0; pos < max_pos; pos++) {
                if (lhs_digits - pos == 0) {
                    //Ran out of digits on the LHS;
                    //prioritise the shorter input
                    return LHS_FIRST;
                }
                else if (rhs_digits - pos == 0) {
                    //Ran out of digits on the RHS;
                    //prioritise the shorter input
                    return RHS_FIRST;
                }
                else {
                    const auto lhs_x = (lhs / static_cast<decltype(BASE)>(std::pow(BASE, lhs_digits - 1 - pos))) % BASE;
                    const auto rhs_x = (rhs / static_cast<decltype(BASE)>(std::pow(BASE, rhs_digits - 1 - pos))) % BASE;

                    if (lhs_x < rhs_x)
                        return LHS_FIRST;
                    else if (rhs_x < lhs_x)
                        return RHS_FIRST;
                }
            }

            //If we reached the end and everything still
            //matches up, then something probably went wrong
            //as I'd have expected to catch this in the tests
            //for equality.
            assert("Unknown case encountered");
        }
    );

    std::cout << '{';
    for (auto x : input)
        std::cout << x << ", ";
    std::cout << '}';

    //Output: { -160, -24, -50, 1, 100, 21, 22, 927, 99, }
}

Demo

Es gibt schnellere Wege, um berechnen Sie die Anzahl der Ziffern in einer Zahl, aber der oben wird Ihnen den Einstieg.

Ich glaube, die folgenden Werke als eine Art Vergleich-Funktion für positive ganze zahlen sind, sofern der integer-Typ verwendet wird, ist wesentlich schmaler als die double Typ (z.B. 32-bit - int - und 64-bit -double) und die log10 routine verwendet, gibt genau die richtigen Ergebnisse für die genauen Potenzen von 10 (was eine gute Implementierung hat):

static const double limit = .5 * (log(INT_MAX) - log(INT_MAX-1));

double lx = log10(x);
double ly = log10(y);
double fx = lx - floor(lx);  //Get the mantissa of lx.
double fy = ly - floor(ly);  //Get the mantissa of ly.
return fabs(fx - fy) < limit ? lx < ly : fx < fy;

Es funktioniert durch den Vergleich der mantissas der Logarithmen. Die mantissas die Nachkommastellen des Logarithmus, und Sie zeigen den Wert der signifikanten stellen einer Zahl ohne den Umfang (z.B. die Logarithmen von 31, 3.1 und 310 haben genau die gleiche Mantisse).

Zweck der fabs(fx - fy) < limit ist es, für Fehler bei der Einnahme der Logarithmus, die auftreten, weil beide Implementierungen log10 sind unvollkommen, und da die floating-point-format Kräfte einige Fehler. (Der integer-Teile von den Logarithmen von 31 und 310 verwenden eine unterschiedliche Anzahl von bits, so gibt es eine unterschiedliche Anzahl von bits für die Mantisse, so dass Sie am Ende abgerundet, um leicht unterschiedliche Werte.) Solange der integer-Typ ist wesentlich schmaler als die double Typ, der berechnet limit wird viel größer sein, als die Fehler in log10. So, der test fabs(fx - fy) < limit im wesentlichen sagt uns, ob zwei berechnete mantissas wäre gleich, wenn exakt berechnet.

Wenn die mantissas unterscheiden, zeigen Sie die lexikographische Ordnung, also kehren wir fx < fy. Wenn Sie gleich sind, dann der ganzzahlige Anteil des Logarithmus sagt uns das Bestellformular ein, damit wir zurück lx < ly.

Es ist einfach um zu testen, ob log10 korrekte Ergebnisse zurückgegeben, für jede Leistung von zehn, da es so wenige von Ihnen gibt. Wenn nicht, Anpassungen können leicht vorgenommen werden: Einfügen if (1-fx < limit) fx = 0; if (1-fu < limit) fy = 0;. Dies ermöglicht, wenn log10 gibt so etwas wie 4.99999... wenn es sollte zurückgegeben haben, 5.

Diese Methode hat den Vorteil, nicht mit Schleifen oder division (die ist zeitaufwendig, die auf vielen Prozessoren).

Eine kompakte Lösung, wenn alle Ihre zahlen sind von nicht negativer und Sie sind klein genug, so dass die Multiplikation um 10 nicht zu einem überlauf führen:

template<class T> bool lex_less(T a, T b) {
  unsigned la = 1, lb = 1;
  for (T t = a; t > 9; t /= 10) ++la;
  for (T t = b; t > 9; t /= 10) ++lb;
  const bool ll = la < lb;
  while (la > lb) { b *= 10; ++lb; }
  while (lb > la) { a *= 10; ++la; }
  return a == b ? ll : a < b;
}

Führen Sie es wie folgt:

#include <iostream>
#include <algorithm>
int main(int, char **) {
  unsigned short input[] = { 100, 21 , 22 , 99 , 1  , 927 };
  unsigned input_size = sizeof(input) / sizeof(input[0]);
  std::sort(input, input + input_size, lex_less<unsigned short>);
  for (unsigned i = 0; i < input_size; ++i) {
    std::cout << ' ' << input[i];
  }
  std::cout << std::endl;
  return 0;
}

Überlastung der < operator zum vergleichen von zwei ganzen zahlen lexikographisch. Für jede ganze Zahl, finden die kleinste 10^k, die nicht weniger als die angegebene Ganzzahl. Vergleichen Sie die Ziffern nacheinander.

class CmpIntLex {
int up_10pow(int n) {
  int ans = 1;
  while (ans < n) ans *= 10;
  return ans;
}
public: 
bool operator ()(int v1, int v2) {
   int ceil1 = up_10pow(v1), ceil2 = up_10pow(v2);
   while ( ceil1 != 0 && ceil2 != 0) {
      if (v1 / ceil1  < v2 / ceil2) return true;
      else if (v1 / ceil1 > v2 / ceil2) return false;
      ceil1 /= 10; 
      ceil2 /= 10;
   }
   if (v1 < v2) return true;
   return false;
}
int main() {
vector<int> vi = {12,45,12134,85};
sort(vi.begin(), vi.end(), CmpIntLex());
}

Ist hier der dumme Lösung, die keine floating-point-tricks. Es ist so ziemlich das gleiche wie der string-Vergleich, aber nicht ein string pro sagen, nicht auch mit negativen zahlen, das zu tun, fügen Sie eine Sektion an der Spitze...

bool comp(int l, int r)
{
  int lv[10] = {}; //probably possible to get this from numeric_limits
  int rv[10] = {};

  int lc = 10; //ditto
  int rc = 10;
  while (l || r)
  {
    if (l)
    {
      auto t = l / 10;
      lv[--lc] = l - (t * 10);
      l = t;
    }
    if (r)
    {
      auto t = r / 10;
      rv[--rc] = r - (t * 10);
      r = t;
    }
  }
  while (lc < 10 && rc < 10)
  {
    if (lv[lc] == rv[rc])
    {
      lc++;
      rc++;
    }
    else
      return lv[lc] < rv[rc];
  }
  return lc > rc;
}

Es ist schnell, und ich bin sicher, es ist möglich es schneller zu machen, immer noch, aber es funktioniert und es ist dumm genug, um zu verstehen...

EDIT: ich aß dump viel code, aber hier ist ein Vergleich aller Lösungen so weit..

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <random>
#include <vector>
#include <utility>
#include <cmath>
#include <cassert>
#include <chrono>

std::pair<int, int> lexicographic_pair_helper(int p, int maxDigits)
{
  int digits = std::log10(p);
  int l = p*std::pow(10, maxDigits-digits);
  return {l, p};
}

bool l_comp(int l, int r)
{
  int lv[10] = {}; //probably possible to get this from numeric_limits
  int rv[10] = {};

  int lc = 10; //ditto
  int rc = 10;
  while (l || r)
  {
    if (l)
    {
      auto t = l / 10;
      lv[--lc] = l - (t * 10);
      l = t;
    }
    if (r)
    {
      auto t = r / 10;
      rv[--rc] = r - (t * 10);
      r = t;
    }
  }
  while (lc < 10 && rc < 10)
  {
    if (lv[lc] == rv[rc])
    {
      lc++;
      rc++;
    }
    else
      return lv[lc] < rv[rc];
  }
  return lc > rc;
}

int up_10pow(int n) {
  int ans = 1;
  while (ans < n) ans *= 10;
  return ans;
}
bool l_comp2(int v1, int v2) {
  int n1 = up_10pow(v1), n2 = up_10pow(v2);
  while ( v1 != 0 && v2 != 0) {
    if (v1 / n1  < v2 / n2) return true;
    else if (v1 / n1 > v2 / n2) return false;
    v1 /= 10;
    v2 /= 10;
    n1 /= 10;
    n2 /= 10;
  }
  if (v1 == 0 && v2 != 0) return true;
  return false;
}

int main()
{
  std::vector<int> numbers;
  {
    constexpr int number_of_elements = 1E6;
    std::random_device rd;
    std::mt19937 gen( rd() );
    std::uniform_int_distribution<> dist;
    for(int i = 0; i < number_of_elements; ++i) numbers.push_back( dist(gen) );
  }

  std::vector<int> lo(numbers);
  std::vector<int> dyp(numbers);
  std::vector<int> nim(numbers);
  std::vector<int> nb(numbers);

  std::cout << "starting..." << std::endl;

  {

    auto start = std::chrono::high_resolution_clock::now();
    /**
    * Sorts the array lexicographically.
    *
    * The trick is that we have to compare digits left-to-right
    * (considering typical Latin decimal notation) and that each of
    * two numbers to compare may have a different number of digits.
    *
    * This probably isn't very efficient, so I wouldn't do it on
    * "millions" of numbers. But, it works...
    */
    std::sort(
    std::begin(lo),
              std::end(lo),
              [](int lhs, int rhs) -> bool {
                //Returns true if lhs < rhs
                //Returns false otherwise
                const auto BASE      = 10;
                const bool LHS_FIRST = true;
                const bool RHS_FIRST = false;
                const bool EQUAL     = false;


                //There's no point in doing anything at all
                //if both inputs are the same; strict-weak
                //ordering requires that we return `false`
                //in this case.
                if (lhs == rhs) {
                  return EQUAL;
                }

                //Compensate for sign
                if (lhs < 0 && rhs < 0) {
                  //When both are negative, sign on its own yields
                  //no clear ordering between the two arguments.
                  //
                  //Remove the sign and continue as for positive
                  //numbers.
                  lhs *= -1;
                  rhs *= -1;
                }
                else if (lhs < 0) {
                  //When the LHS is negative but the RHS is not,
              //consider the LHS "first" always as we wish to
              //prioritise the leading '-'.
              return LHS_FIRST;
                }
                else if (rhs < 0) {
                  //When the RHS is negative but the LHS is not,
              //consider the RHS "first" always as we wish to
              //prioritise the leading '-'.
              return RHS_FIRST;
                }

                //Counting the number of digits in both the LHS and RHS
                //arguments is *almost* trivial.
                const auto lhs_digits = (
                lhs == 0
                ? 1
                : std::ceil(std::log(lhs+1)/std::log(BASE))
                );

                const auto rhs_digits = (
                rhs == 0
                ? 1
                : std::ceil(std::log(rhs+1)/std::log(BASE))
                );

                //Now we loop through the positions, left-to-right,
              //calculating the digit at these positions for each
              //input, and comparing them numerically. The
              //lexicographic nature of the sorting comes from the
              //fact that we are doing this per-digit comparison
              //rather than considering the input value as a whole.
              const auto max_pos = std::max(lhs_digits, rhs_digits);
              for (auto pos = 0; pos < max_pos; pos++) {
                if (lhs_digits - pos == 0) {
                  //Ran out of digits on the LHS;
                  //prioritise the shorter input
                  return LHS_FIRST;
                }
                else if (rhs_digits - pos == 0) {
                  //Ran out of digits on the RHS;
                  //prioritise the shorter input
                  return RHS_FIRST;
                }
                else {
                  const auto lhs_x = (lhs / static_cast<decltype(BASE)>(std::pow(BASE, lhs_digits - 1 - pos))) % BASE;
                  const auto rhs_x = (rhs / static_cast<decltype(BASE)>(std::pow(BASE, rhs_digits - 1 - pos))) % BASE;

                  if (lhs_x < rhs_x)
                    return LHS_FIRST;
                  else if (rhs_x < lhs_x)
                    return RHS_FIRST;
                }
              }

              //If we reached the end and everything still
              //matches up, then something probably went wrong
              //as I'd have expected to catch this in the tests
              //for equality.
              assert("Unknown case encountered");
              }
              );

    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = end - start;
    std::cout << "Lightness: " << elapsed.count() << '\n';
  }

  {
    auto start = std::chrono::high_resolution_clock::now();

    auto max = *std::max_element(begin(dyp), end(dyp));
    int maxDigits = std::log10(max);

    std::vector<std::pair<int,int>> temp;
    temp.reserve(dyp.size());
    for(auto const& e : dyp) temp.push_back( lexicographic_pair_helper(e, maxDigits) );

    std::sort(begin(temp), end(temp), [](std::pair<int, int> const& l, std::pair<int, int> const& r)
    { if(l.first < r.first) return true; if(l.first > r.first) return false; return l.second < r.second; });

    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = end - start;
    std::cout << "Dyp: " << elapsed.count() << '\n';
  }

  {
    auto start = std::chrono::high_resolution_clock::now();
    std::sort (nim.begin(), nim.end(), l_comp);
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = end - start;
    std::cout << "Nim: " << elapsed.count() << '\n';
  }

//  {
//    auto start = std::chrono::high_resolution_clock::now();
//    std::sort (nb.begin(), nb.end(), l_comp2);
//    auto end = std::chrono::high_resolution_clock::now();
//    auto elapsed = end - start;
//    std::cout << "notbad: " << elapsed.count() << '\n';
//  }

  std::cout << (nim == lo) << std::endl;
  std::cout << (nim == dyp) << std::endl;
  std::cout << (lo == dyp) << std::endl;
//  std::cout << (lo == nb) << std::endl;
}