char array mit Seperator alphabetisch sortieren

SeppJ

In Einzelworte einteilen und sortieren gibt's auch in C++, aber das dürfte ähnlich ineffizient sein wie in C#, Zeichenkettenoperationen sind nun einmal teuer. Jedoch:

Dazu zu sagen ist noch dass ich das Ganze in extrem effizient brauche, da die Arrays eine durchschnittliche Länge von 50000 - 100000 Zeichen haben und der Sortiervorgang mehrmals pro Sekunde ausgeführt werden muss.

Das passt nicht wirklich zusammen. 50-100k und mehrmals pro Sekunde, das sind ein paar MB zu verarbeitende Daten pro Sekunde. Schätz mal, wie schnell dein Computer ist. Wenn da nicht mindestens 1000x mehr rauskommt, dann rüste mal deinen 20 Jahre alten Rechner auf.

Ganz naiv implementiert:
http://ideone.com/k85dzw

Das ist jetzt aber über 10 Ecken, von denen man sicherlich einige sparen könnte. Ich habe schon zwei Ecken gespart, indem ich sagte, dass du kein char-Array möchtest, sondern string. Dann beschäftigt sich der große Rest des Codes damit, diesen auseinander und wieder zusammen zu setzen und ein kleiner Teil sortiert einmal etwas (nach ASCII-Reihenfolge, der Standardvergleichsrelation. Für alphabetisches Sortieren musst du eine andere Sortierrelation angeben). Vieles davon könnte man sich sparen, wenn man:
-eventuell mehr Information über die Eingabe hätte. Dieser Code kommt mit beliebig langen Eingaben und beliebig langen Wörtern zurecht. Knivil hat schon eine Indexliste vorgeschlagen, was eine Möglichkeit wäre, die etwas bringen könnte. Mir fallen auch noch andere ein, aber im allgemeinsten Fall würde ich erst einmal meine Lösung nehmen.
-sich fragt, ob das char-Array als Start und Ziel überhaupt wirklich gewünscht sind oder aus Unwissen über bessere Möglichkeiten entspringen. Wenn man hier direkt aus der eigentlichen Quelle (im Beispiel cin) in den Wörtervector lesen würde, dann wäre schon viel gewonnen. Und direkt in das Ziel schreiben (hier cout). Aber es war ja der Umweg über die Zeichenketten verlangt.

.. ja gibt's schon (Code hinknall):

#include <algorithm> // sort
#include <iterator> // ostream_iterator
#include <string>
#include <iostream>
#include <sstream> // stringstream
#include <vector>

int main()
{
    using namespace std;
    char wordList[] = "cTest aaa xyz abcd Abcd usw bWort";

    istringstream in( wordList );
    vector< string > words( (istream_iterator< string >( in )), istream_iterator< string >() );
    sort( words.begin(), words.end() );
    ostringstream out;
    copy( words.begin(), words.end(), ostream_iterator< string >( out, " " ) );
    string result = out.str();

    cout << "Ergebnis: [" << result << "]" << endl;
}

Columbo

Edit: Der Code ist leider völlig falsch, ich vergleiche nur die ersten Zeichen... *patsch*

happystudent

EDIT: Oha, so viele neue Anworten

Columbo

Hier meine Version, braucht für eine Million Zeichen bei mir (clang 3.3, -O2)
etwa 20 Millisekunden:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
	char wordList[1000000];

	srand(time(nullptr));
	for( std::size_t i = 0; i != sizeof(wordList); ++i )
		wordList[i] = ( i % 5 ? rand() % 256 : ' ' );

	struct wordInformation
	{
		char const* pos;
		std::size_t len;
	};

	clock_t first = clock();

	std::vector<wordInformation> vec;
	vec.reserve( sizeof(wordList) / 5 ); // Durchschnittliche Wortlänge +1 (Edit: Ich meine, der Divisor ist die ...)

	bool last_char = false;
	for( auto p = wordList; p != wordList + sizeof(wordList); ++p )
	{
		if( std::isalpha(*p) )
		{
			if(!last_char)
			{
				vec.push_back({p, 1});
				last_char = true;
			}
			else
				++vec.back().len;
		}
		else if(last_char)
			last_char = false;
	}

	std::sort( std::begin(vec), std::end(vec), [](wordInformation const& p1,
	                                              wordInformation const& p2)
	                                           { return std::lexicographical_compare(p1.pos, p1.pos + p1.len,
	                                                                                 p2.pos, p2.pos + p2.len); } );

	char sortedWordList[sizeof(wordList)];

	auto ptr = sortedWordList;
	for( auto& info : vec )
	{
		while( info.len-- )
			*ptr++ = *info.pos++;
		*ptr++ = ' ';
	}

	std::cout << (clock() - first) / float(CLOCKS_PER_SEC);
}

Ich bin mir aber immer noch nicht sicher, ob es überhaupt korrekt ist...

Edit: Bug gefixt.
Edit²: Das war gar kein Bug...

Columbo

Nun, dein Beispiel wird korrekt sortiert: https://ideone.com/mB6TTv

happystudent

SeppJ schrieb:

Ganz naiv implementiert:
http://ideone.com/k85dzw

Das ist jetzt aber über 10 Ecken, von denen man sicherlich einige sparen könnte. Ich habe schon zwei Ecken gespart, indem ich sagte, dass du kein char-Array möchtest, sondern string. Dann beschäftigt sich der große Rest des Codes damit, diesen auseinander und wieder zusammen zu setzen und ein kleiner Teil sortiert einmal etwas (nach ASCII-Reihenfolge, der Standardvergleichsrelation. Für alphabetisches Sortieren musst du eine andere Sortierrelation angeben). Vieles davon könnte man sich sparen, wenn man:
-eventuell mehr Information über die Eingabe hätte. Dieser Code kommt mit beliebig langen Eingaben und beliebig langen Wörtern zurecht. Knivil hat schon eine Indexliste vorgeschlagen, was eine Möglichkeit wäre, die etwas bringen könnte. Mir fallen auch noch andere ein, aber im allgemeinsten Fall würde ich erst einmal meine Lösung nehmen.
-sich fragt, ob das char-Array als Start und Ziel überhaupt wirklich gewünscht sind oder aus Unwissen über bessere Möglichkeiten entspringen. Wenn man hier direkt aus der eigentlichen Quelle (im Beispiel cin) in den Wörtervector lesen würde, dann wäre schon viel gewonnen. Und direkt in das Ziel schreiben (hier cout). Aber es war ja der Umweg über die Zeichenketten verlangt.

Danke schonmal dafür. Also ich brauche ein char array weil ich eine Funktion von einer dll verwende, welche ein char array als Parameter haben will.

Dann gebe ich hier mal alle relevanten Informationen:

- Eingabe kann beliebig lang sein, hat aber eine Untergrenze von ca 50000.
- Wörter können auch beliebig lang sein.
- Wörter bestehen aus Buchstaben (klein und groß), Zahlen und underscore.
- Wörter können nur mit Buchstaben oder underscore anfangen.

Ich werde das heute Nachmittag gleich mal ausprobieren.

Arcoth schrieb:

Hier meine Version, braucht für eine Million Zeichen bei mir (clang 3.3, -O2)
etwa 20 Millisekunden:

Danke, werd ich mir auch anschauen!

volkard

Arcoth schrieb:

struct wordInformation
	{

Gut.

Columbo

- Wörter bestehen aus Buchstaben (klein und groß), Zahlen und underscore.
- Wörter können nur mit Buchstaben oder underscore anfangen.

Das ist sehr wichtig.

Außerdem: Wie möchtest du bspw. die Rangfolge von _ und a und A haben? _ zuerst? Denn wenn ich mit der angepassten Version dein Beispiel kompiliere, dann kommt folgende Sortierung heraus:

_cT68est aaa xyz abc_79d A_bcd usw8 bWort
=>
A_bcd _cT68est aaa abc_79d bWort usw8 xyz

Das heißt, ein einfacher Vergleich der ASCII-Werte ist ggf. zu primitiv.

knivil

Das ist sehr wichtig.

Nicht wirklich, wichtiger ist die Ordnungsrelation, also lexikographisch, alphabetisch, ... whatever.

struct sidx
{
    char const* pos;
    unsigned int len;
};

void split_idx(std::string const& words, std::vector<sidx>& indices)
{
    indices.clear();
    if (words.length() == 0) return;

    sidx idx = { 0, 0 };
    char const* p = &words[0];
    char const* pend = p + words.length();
    bool inword = false;
    while(p != pend)
    {
        bool change = ((bool)std::isalnum(*p)) != inword;
        if (change)
        {
            if (inword)
            {
                idx.len = p - idx.pos;
                indices.push_back(idx);
            }
            else
            {
                idx.pos = p;
            }
            inword = !inword;
        }
        ++p;
    };

    // close open word indexes
    if (inword)
    {
        idx.len = p - idx.pos;
        indices.push_back(idx);
    }
}

Hier meine split-Funktion, den Rest, also combine, gibt es ja schon. Das klassische RLE halt. std::alnum kann gern durch ein anderes Kriterium ersetzt werden.

Es gibt da einige kleine Anmerkungen von mir:

else 
                 ++vec.back().len;

Nun, das habe ich mir gespart.

if(last_char) 
             last_char = false;

Also wenn last_char == true -> last_char = false, ansonsten bleibe einfach false ... warum nicht einfach:

last_char = false

happystudent

Wow, das ist ja endlich mal ein richtig aktives Forum

Also die Reihenfolge sollte sein:

- Ersteinmal unabhänig von der Groß/Kleinschreibung, aber bei gleichen Buchstaben zuerst Kleinbuchstaben, dann Großbuchstaben
- Underscore als letztes

Also das Beispiel:

_cT68est aaa xyz abc_79d A_bcd usw8 bWort

Sollte sortiert so aussehen:

aaa abc_79d A_bcd bWort usw8 xyz _cT68est

knivil

- Ersteinmal unabhänig von der Groß/Kleinschreibung, aber bei gleichen Buchstaben zuerst Kleinbuchstaben, dann Großbuchstaben
- Underscore als letztes

Kannste alleine machen, indem das Sortierkritierium angepasst wird.

happystudent

Jo, werd ich machen. Das war eh schon mehr Hilfe als ich mir erhofft hatte

volkard

struct myLess{
    static int f(char x){
        return (((x&31))<<1)-(x>>5);
    }
    bool operator()(char a,char b){
        return f(a)<f(b);
    }
};
…
std::sort( std::begin(vec), std::end(vec), [](wordInformation const& p1,
wordInformation const& p2)
{ return std::lexicographical_compare(p1.pos, p1.pos + p1.len,
p2.pos, p2.pos + p2.len,myLess()); } );

SeppJ

happystudent schrieb:

Danke schonmal dafür. Also ich brauche ein char array weil ich eine Funktion von einer dll verwende, welche ein char array als Parameter haben will.

Sofern das Ding ein const char* will, passt da auch ein std::string. Falls das Ding da wirklich reinschreibt, dann eigentlich auch, wenn du den String vorher passend groß machst. 100k Zeichen auf dem Stack klingen nämlich nicht nach so einer tollen Idee.

Werner Salomon

happystudent schrieb:

Also ich brauche ein char array weil ich eine Funktion von einer dll verwende, welche ein char array als Parameter haben will.

Ist diese Funktion der Input oder der Output? und wie sieht die jeweils andere Seite aus?

happystudent

Hm ja, also eigentlich will die dll Funktion ein const char * als Parameter, die wird an dem Ding also nichts verändern.

Ich muss aber ein nicht-konstantes char array nehmen, weil ich vor und nach dem dll Aufruf selbiges schon verändere (also mein Programm führt die Veränderungen durch, nicht die dll).

EDIT:

Werner Salomon schrieb:

happystudent schrieb:

Also ich brauche ein char array weil ich eine Funktion von einer dll verwende, welche ein char array als Parameter haben will.

Ist diese Funktion der Input oder der Output? und wie sieht die jeweils andere Seite aus?

Äh, also die Funktion sorgt letztendlich für einen Output. Input ist das char array.

Werner Salomon

happystudent schrieb:

Äh, also die Funktion sorgt letztendlich für einen Output. Input ist das char array.

.. und wie kommen die Zeichen in das char array? (wordList s.o.)

happystudent

Also die werden in einer ziemlich fetten include Datei beim Programmstart zugewiesen (das Programm beginnt immer mit dem gleichen char array).

Also das sieht etwa so aus (Phantasiewörter):

char wordList[] = "aaa bzcc xpy wgggh iooo"
                  "kjl arhz wwwo plmg tttt"
                  "lalaa gggk fffr ccoe gd"
                  /* usw usw */

Werner Salomon

happystudent schrieb:

Also die werden in einer ziemlich fetten include Datei beim Programmstart zugewiesen (das Programm beginnt immer mit dem gleichen char array).

Also das sieht etwa so aus (Phantasiewörter):
char wordList[] = "aaa bzcc xpy wgggh iooo"
                  "kjl arhz wwwo plmg tttt"
                  "lalaa gggk fffr ccoe gd"
                  /* usw usw */

.. und wie erklärt sich dann die Anforderung, dass da mehrere dieser wordList's pro Sekunde sortiert werden sollen. Das ist doch erst mal nur eine?