4programmers.net 4p Forum C/C++ zbiór słów"

zbiór słów"

zbiór słów"
Niikelion
NI
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: Warszawa
  • Postów: 535
0

Zawsze gdy miałem w programie zbiór dostępnych słów był to wektor stringów. Przy paru wyrazach nie ma problemu ale przy paru tysiącach już jest... Spróbowałem to zrobić bez wektora i wyszło mi takie coś:
types.h

Kopiuj
#ifndef TYPES_H
#define TYPES_H

#include<cstdlib>
#include<iostream>

struct Alphabet
{
    char letters[2][26];
    Alphabet();
    Alphabet(const Alphabet & target);
    ~Alphabet();
};

class StringMap
{
    StringMap**cells;
    unsigned int number;
public:
    void add(std::string source,Alphabet alph);
    bool contains(std::string source,Alphabet alph);
    StringMap();
    StringMap(const StringMap & target);
    ~StringMap();
};

#endif // TYPES_H

types.cpp

Kopiuj
#include "types.h"

Alphabet::Alphabet()
{
    for (unsigned short i=0; i<26; i++)
    {
        letters[0][i]='a'+i;
        letters[1][i]='a'+i;
    }
}

Alphabet::Alphabet(const Alphabet & target)
{
    for (unsigned short i=0; i<26; i++)
    {
        letters[0][i]=target.letters[0][i];
        letters[1][i]=target.letters[1][i];
    }
}

Alphabet::~Alphabet(){}

void StringMap::add(std::string source,Alphabet alph)
{
    if (!contains(source,alph))
    {
        StringMap*next=this;
        int num=0;
        for (unsigned int i=0; i<source.size(); i++)
        {
            num=-1;
            for (unsigned short j=0; j<26; j++)
            {
                if (alph.letters[0][j]==source[i])
                {
                    num=j;
                    break;
                }
                else if (alph.letters[1][j]==source[i])
                {
                    num=26+j;
                    break;
                }
            }
            if (num==-1)
                break;
            if (next->cells[num]!=NULL)
            {
                next->cells[num]->number++;
            }
            else
                next->cells[num]=new StringMap;

            next=next->cells[num];
        }
    }
}

bool StringMap::contains(std::string source,Alphabet alph)
{
    int num=0;
    unsigned int pos=0;
    StringMap * next=this;
    for (unsigned int i=0; i<source.size(); i++)
    {
        num=-1;
        for (unsigned int j=0; j<26; j++)
        {
            if (alph.letters[0][j]==source[i])
            {
                num=j;
                break;
            }
            else if (alph.letters[1][j]==source[i])
            {
                num=j+26;
                break;
            }
        }
        if (num==-1)
            break;
        if (next->cells[num]==NULL)
        {
            return false;
        }
        next=next->cells[num];
        pos=next->number;
    }
    for (unsigned int i=0; i<52; i++)
        if (next->cells[i]!=NULL and next->cells[i]->number==pos)
            return false;
    return true;
}

StringMap::StringMap()
{
    cells=new StringMap*[52];
    for (unsigned int i=0; i<52; i++)
        cells[i]=NULL;
    number=0;
}

StringMap::StringMap(const StringMap & target)
{
    cells=new StringMap*[52];
    for (unsigned int i=0; i<52; i++)
    {
        if (target.cells[i]!=NULL)
        {
            cells[i]=new StringMap(*target.cells[i]);
        }
        else
            cells[i]=NULL;
    }
}

StringMap::~StringMap()
{
    for (unsigned short i=0; i<52; i++)
        if (cells[i]!=NULL)
            delete cells[i];
    delete[] cells;
}

niestety pojawiają się losowe błędy, na przykład mówi że nie ma jakiegoś słowa gdy wiele słów nachodzi na nie(w całości) albo mówi, że jakieś jest, mimo że nie zostało dodane. Nie wiem gdzie jest błąd, kod piszę od nowa 3 raz z tym samym efektem.

Udostępnij
Komentuj
some_ONE
SO
  • Rejestracja: dni
  • Ostatnio: dni
2

Może zacznijmy od tego co chcesz osiągnąć, bo zdaje mi się, że do przechowywania zbioru słów wystarczy unordered_set.

Udostępnij
Komentuj
Niikelion
NI
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: Warszawa
  • Postów: 535
0

wiem, że już ktoś coś potrzebnego do tego zrobił, ale nie chcę korzystać z gotowca

Udostępnij
Komentuj
Niikelion
NI
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: Warszawa
  • Postów: 535
0

Chcę doprowadzić moją klasę do stanu używalności-usunąć błędy związane z szukaniem(a przynajmniej mnie się tak wydaje, że to błędy szukania a nie zapisywania)

Udostępnij
Komentuj
stryku
stryku
  • Rejestracja: dni
  • Ostatnio: dni
  • Postów: 607
2

Wiem, że nie prosiłeś o to, ale takie rzeczy wyłapałem.

Kopiuj
for (unsigned short i=0; i<52; i++)

użycie unsigned short w takim miejscu jest żadną optymalizacją, a nawet może spowolnić program bo np. na x86 jeżeli są wykonywane jakieś operacje na "zmiennych" dwu bajtowych to w kodzie maszynowym do kodu operacji dodawany jest dodatkowy bajt prefiksu (0x80 jeżeli dobrze pamiętam), więc rozkaz jest dłuższy => procesor dłużej go wczytuje i wykonuje.
Używanie takich optymalizacji wykonuje się tylko jeżeli bardzo zależy Ci na pamięci. Tu to chyba przesada.

Niekonsekwencja. Jak już używasz unsighed short to używaj wszędzie tam gdzie można.

Nie rozumiem idei struktury Alphabet. W konstruktorze masz

Kopiuj
for (unsigned short i=0; i<26; i++)
    {
        letters[0][i]='a'+i;
        letters[1][i]='a'+i;
    }

Czyli tworzysz dwie tablice z małymi literami. (tak w ogóle to może to jest przyczyną błędów bo po copypajście linijki zapomniałeś zmienić na 'A' :p i Ci program nie ogarnia dużych liter)

Mimo wszystko idei nie rozumiem. Bo potem robisz takie cudo

Kopiuj
for (unsigned int j=0; j<26; j++)
        {
            if (alph.letters[0][j]==source[i])
            {
                num=j;
                break;
            }
            else if (alph.letters[1][j]==source[i])
            {
                num=j+26;
                break;
            }
        }

Czyli porównujesz kolejny znak słowa z kolejnym znakiem alfabetu małymi i dużymi i przypisuje do num małą wersję znaku (chyba). I za nic nie ogarnę po co ten cały alfabet. Czemu nie zrobisz tak

Kopiuj
for (char c = 'a'; c <= 'z'; ++c)
        {
            if (source[i] == c)
            {
                num=j;
                break;
            }
            else if (source[i] == c - 32)
            {
                num=c + 32; //czemu tu bylo 26?
                break;
            }
        }

Tyle że to dalej lipa bo ta pętla tu tylko zawadza

Kopiuj
if( isalpha( source[i] ) )
    num = tolower( source[i] );

A tak już w ogóle to wydaje mi się, że chcesz zaimplementować coś w stylu drzewa Trie (https://en.wikipedia.org/wiki/Trie). Czemu nie skorzystasz z jakiejś gotowej implementacji?

A tak już w ogóle, w ogóle to na prawdę warto się męczyć dla tych paru KB RAMu zamiast użyć unordered_set?

Udostępnij
Komentuj
Niikelion
NI
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: Warszawa
  • Postów: 535
0

To short to tak z automatu walnąłem :) Struktura Alphabet jest dlatego, że używam różnych alfabetów np polski lub niemiecki

Kopiuj
Alphabet alph;
alph.letters[0][numer]//podstawowe litery,np a ,b ,c itd, najczęściej zwyczajny angielski alfabet
alph.letters[1][numer]//dodatkowe litery ą,ć,ł itd,najczęściej dodatkowe litery, które nie zmieściły się w podstawowej części
Udostępnij
Komentuj
Niikelion
NI
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: Warszawa
  • Postów: 535
0

Sprawdziłem dokładniej co nie działa i zauważyłem, że problem pojawia się w tedy, kiedy dodaję nowe słowo, które jest częścią innego, losowy przykład:

Kopiuj
eloo//dodaje
 elo//dodaje
el//wykrywa jako dodane, jak dodam poprzednie słowa w odwrotnej kolejności to nie ma problemu
Udostępnij
Komentuj

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.

Utwórz konto