zbiór słów"

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

#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

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

2

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

0

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

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)

2

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

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

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

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

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

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?

0

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

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
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:

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1