zbiór słów" :: 4programmers.net

Rejestracja:około 11 lat
Ostatnio:około 5 lat
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.

edytowany 2x, ostatnio: Niikelion 2016-01-20 21:54

some_ONE

2016-01-20 21:54

some_ONE2016-01-20 21:54

Rejestracja:ponad 10 lat
Ostatnio:około rok

2

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

Niikelion

2016-01-20 21:58

Niikelion2016-01-20 21:58

Rejestracja:około 11 lat
Ostatnio:około 5 lat
Lokalizacja:Warszawa
Postów:535

0

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

edytowany 1x, ostatnio: Niikelion 2016-01-20 22:01

kq 2016-01-20 22:06

to wróćmy do tego co chesz osiągnąć.

Niikelion

2016-01-20 22:19

Niikelion2016-01-20 22:19

Rejestracja:około 11 lat
Ostatnio:około 5 lat
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)

stryku

2016-01-20 23:07

stryku2016-01-20 23:07

Rejestracja:ponad 11 lat
Ostatnio:prawie 2 lata
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?

edytowany 2x, ostatnio: stryku 2016-01-20 23:10

_13th_Dragon 2016-01-20 23:15

implementacja Trie - daje naprawdę świetne wyniki, 10-krotnie mniejszy (albo i lepiej) rozmiar w pamięci niż mapa, wszystko zależy od ilości słów.

stryku 2016-01-20 23:23

@_13th_Dragon Ja wiem, ale @Niikelion pisał o paru tysiącach, więc wątpie, żeby zabawa z Trie była w tym przypadku opłacalna

_13th_Dragon 2016-01-20 23:30

Przy paru tysiącach może już zacząć być opłacalna, przy sensownej budowie tego Trie oczywiście.

Niikelion 2016-01-21 06:51

faktycznie to short nie wiele daje, a o tym że może spowalniać to nie wiedziałem :)

Niikelion

2016-01-21 06:50

Niikelion2016-01-21 06:50

Rejestracja:około 11 lat
Ostatnio:około 5 lat
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

Niikelion

2016-01-21 07:27

Niikelion2016-01-21 07:27

Rejestracja:około 11 lat
Ostatnio:około 5 lat
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

zbiór słów"

Niikelion

some_ONE

Niikelion

Niikelion

stryku

Niikelion

Niikelion

Programista Systemów Automatyki - PCS7

PHP + Codeigniter 4 programista, aplikacja do fakturowania

DevOps Engineer - migracja serwerów (Kubernetes,Docker,RoR)

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami