Ganzzahlige Zeichenfolge ("A", "B", .... "Z", "AA", "AB" ...)

95778
James Khoury

Diese Frage wird also durch zwei Dinge ausgelöst.

  1. Ich habe in unserer Quellcodeverwaltung Code gefunden, der diese Art von Dingen erledigt.
  2. Diese SO-Fragen:

Als ich über dieses Problem nachdachte, kam mir dies fast sofort in den Kopf.

class Util
{
    private static string[] alphabetArray = { string.Empty, "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };
    public static IEnumerable<string> alphaList = alphabetArray.Cast<string>();

    public static string IntToAA(int value)
    {
        while (Util.alphaList.Count() -1 < value)
        {
            Util.IncreaseList();
        }

        return Util.alphaList.ElementAt(value);
    }

    private static void IncreaseList()
    {
        Util.alphaList = Util.alphabetArray.Take(1).Union(
            Util.alphaList.SelectMany(currentLetter =>
               Util.alphabetArray.Skip(1).Select(innerLetter => currentLetter + innerLetter)
            )
        );
    }
}

Meine Frage ist folgende: Ist dieser Ansatz eine bessere Lösung (leistungsmäßig)? oder ist ein rekursiver / berechneter Wert besser (z. B. diese Antwort )?

Antworten
28
Die wiederholte Durchführung trivialer Transformationen mit LINQ schadet immer der Leistung. Wenn Sie speziell Leistung wünschen, halten Sie sich von LINQ fern. Jeff Mercado vor 7 Jahren 3
@JeffMercado jeff Ich sehe nicht, dass die Werte viel über 50 hinausgehen, also würden sie nur einmal / zweimal getroffen. Was soll ich dann konkret ändern? James Khoury vor 7 Jahren 0

2 Antworten auf die Frage

27
BenVlodgi

Math! Simple math is certainly the nicest way, no lists to deal with, just old fashion ASCII and math. If you want to be able to toggle the capitalization of this method, simply use a ternary operator like this isCapital ? 'A' : 'a' I just left it capital as that is how the OP seemed to want it. Jeff Mercado's Answer explained well enough the differences between calculated, recursive and such... I mostly wanted to provide a simplistic calculated answer that did not involve using lists.

public static string IntToLetters(int value)
{
    string result = string.Empty;
    while (--value >= 0)
    {
        result = (char)('A' + value % 26 ) + result;
        value /= 26;
    }
    return result;
}

Edit: To meet the requirement of A being 1 instead of 0, I've added -- to the while loop condition, and removed the value-- from the end of the loop, if anyone wants this to be 0 for their own purposes, you can reverse the changes, or simply add value++; at the beginning of the entire method.

In Ihrer Version wird 'A' auf 0 und nicht auf 1 gesetzt. Wie möchten Sie dies auf vereinfachte Weise erreichen? James Khoury vor 5 Jahren 1
@JamesKhoury Oh, das tut mir leid. Ich wusste nicht ... nur "value-". Am Anfang der gesamten Methode habe ich tatsächlich extra Längen genommen, um die Basis auf 0 zu setzen. BenVlodgi vor 5 Jahren 1
Das ist großartig. Bietet diese Implementierung eine Leistungssteigerung gegenüber anderen Implementierungen? James Khoury vor 5 Jahren 0
Um 26 Saiten zu fassen, ist dies einfach besser Tuyen Pham vor 4 Jahren 0
Vielleicht möchten Sie einen StringBuilder verwenden und ihn mit einer Kapazität von "value / 26 + 1" initialisieren. HerpDerpington vor 4 Jahren 1
16
Jeff Mercado

Wenn Sie eine Funktion generell aufrufen, erhalten Sie einen kleinen (winzigen) Leistungstreffer. Rekursive Funktionen (AFAIK) können nicht eingebettet werden, so dass sie nicht wegoptimiert werden können. Bei LINQ geht es darum, andere Funktionen aufzurufen. Dies ist die schlechteste Wahl, wenn Sie Code mit guter Leistung schreiben möchten. Ich habe es schon gesagt, LINQ ist nicht für das Schreiben von schnellem Code gedacht, sondern für das Schreiben von prägnantem Code. Dies ist ein einfacher Algorithmus, der sich dadurch nicht verkeilen muss.

* Es hilft nicht, wenn Sie LINQ nicht korrekt verwenden, und Sie haben eine Reihe von No-No-Codes in Ihrem Code.

Wenn Sie den schnellsten Ansatz wünschen (ohne dabei alle möglichen Werte im Speicher abbilden zu müssen), bleiben Sie von diesen entfernt und führen eine direktere Konvertierung durch. Um der absolut Schnellste zu sein, musst du den Low-Level runterholen und nutzenunsafe (nicht verwalteten) Code verwenden. Ich werde nicht dorthin gehen. Wenn Sie jedoch am schnellsten verwalteten Code wünschen, möchten Sie dies iterativ tun. Auf jeden Fall ist mein Vorschlag nicht der Anspruch, die schnellste Implementierung zu sein, es könnte sehr gut nicht sein, aber ich weiß nicht, Sie müssten ein Profil erstellen, um es herauszufinden.

Wir führen eine Basiskonvertierung von Basis-10-Zahlen in Basis-26-"Zahlen" durch. Ich weiß nicht, ob es einen schnelleren Algorithmus dafür gibt, aber hier ist eine direkte Konvertierung unter Verwendung StringBuildereines Puffers.

const int ColumnBase = 26;
const int DigitMax = 7; // ceil(log26(Int32.Max))
const string Digits = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static string IndexToColumn(int index)
{
    if (index <= 0)
        throw new IndexOutOfRangeException("index must be a positive number");

    if (index <= ColumnBase)
        return Digits[index - 1].ToString();

    var sb = new StringBuilder().Append(' ', DigitMax);
    var current = index;
    var offset = DigitMax;
    while (current > 0)
    {
        sb[--offset] = Digits[--current % ColumnBase];
        current /= ColumnBase;
    }
    return sb.ToString(offset, DigitMax - offset);
}

Andererseits können Sie, da Ihre Eingaben auf bis zu 50-Zoll beschränkt sind, nur ein Array (und kein Array IEnumerable<>) für die Suche verwenden.

static readonly string[] Columns = new[]{"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","AA","AB","AC","AD","AE","AF","AG","AH","AI","AJ","AK","AL","AM","AN","AO","AP","AQ","AR","AS","AT","AU","AV","AW","AX","AY","AZ","BA","BB","BC","BD","BE","BF","BG","BH"};
public static string IndexToColumn(int index)
{
    if (index <= 0)
        throw new IndexOutOfRangeException("index must be a positive number");

    return Columns[index - 1];
}
Ich bin verwirrt. Wenn also die Zuordnung der Zahlen in ein In-Memory-Feld schneller ist, warum wäre dies schneller als der von mir vorgeschlagene Ansatz? James Khoury vor 7 Jahren 0
Nun, du machst eine Form von Memo (sehr seltsam könnte ich hinzufügen). Nach dem Aufrufen bestimmter Eingaben wird Ihr Code im Wesentlichen zu einer (linearen) Suche. Sie zahlen jedoch viel, nur um diese Memoisierung zum Laufen zu bringen. Um die entsprechende Spalte für den Index 50 abrufen zu können, mussten Sie alle Werte von 1 bis 49 berechnen (was bei Ihrem ersten Aufruf zu einem noch größeren Treffer führt). Wenn Sie mit Indizes in inkrementeller Reihenfolge auf diese zugreifen (die Kosten für die Verwendung von LINQ werden ignoriert), ist dies in Ordnung. Für eine solche begrenzte Verwendung einer Utility-Methode würde ich ihre Existenz in Frage stellen. Jeff Mercado vor 7 Jahren 0
Es ist also besser, es als "Liste" statt als "IEnumerable" zu behalten, da es sich um einen linearen Look handelt. (vorausgesetzt, die Werte sind vorberechnet?) James Khoury vor 7 Jahren 0
@JamesKhoury Fast alles ist besser als eine lineare Suche. svick vor 7 Jahren 0
@ JeffMercado Ich glaube, LINQ kann verwendet werden, um Code mit guter Leistung zu schreiben, und ich würde es sicherlich nicht als "erste Wahl" bezeichnen. Ja, es hat etwas Overhead, aber das wird die meiste Zeit vernachlässigbar sein. svick vor 7 Jahren 0
@svick Ich glaube, Jeff bezog sich auf die Verwendung von Funktionen über Berechnungen. Wenn Sie eine andere Antwort haben, empfehlen wir Ihnen, eine eigene Antwort einzureichen. James Khoury vor 7 Jahren 0
I found this very helpful, but also needed a reverse - which brought me to the Hexavigesimal wikipedia entry, and allowed me to create this: public static int ConvertStringToInt(string str) { int index = (Digits.IndexOf(str[0]) + 1); for (int i = 1; i Chris vor 6 Jahren 0