[질문]메모리에서 문자열 찾기.. 알려주세요..

leolo의 이미지

지금 저에게 필요한 것은 이런것입니다.
얘를 들어, 12345678 을 던져주면 앞에서 부터 값을 비교하겨 가장 길이가 긴 데이터를 메모리에서 찾는 것입니다.

즉, 메모리에
1, 12, 134, 123이 있는 경우는 123을 찾고,

1, 12345, 123, 1234 가 있으면 12345를 찾고,

1, 142, 143, 1238 이 있으면 1을 찾는 것입니다.

이와 관련된 코드나 아이디어, 또는 참조할 만한 프로젝트가 있으면 좀 부탁드립니다.

익명 사용자의 이미지

ㅡㅡa

문자열의 길이를 오름차순으로 정렬해놓으시면 됩니다..

12345 1234 123 12 가있다고 칠때..

오름차순으로 데이타를 정렬해논경우는 맨첨에 12란 데이터로

검색시 strncmp( "12", "12345", strlen( "12" ) ) == 0 시에

리턴하면됩니다..

익명 사용자의 이미지

오름차순으로 정렬한 다음 strncmp로 또 비교하는 것은 매우 비효율적입니다. 그냥 한번에 스캔하면서 최대값을 비교해도 충분합니다.

익명 사용자의 이미지

오름차순으로 정렬한다는 문구는 오름차순을 매번 정렬한다는 의미가 아니었습니다만.. 자료구조자체를 항상 오름차순으로 유지를 해야한다는 의미였습니다..

leolo의 이미지

결론을 내었습니다.
링크드리스트로 새로운 노드를 추가할 때, 항상 오름차순으로 정렬하고,
인덱싱을 두어 바스켓을 구성하는 것입니다.
예를 들어,
21
223
234

34
345
356
의 데이터가 있으면,
바스켓을 2개 구성하여 메모리에 올리고, 이들을 오름차순으로 정렬하는 형태를 취합니다. 즉, 2로 시작하는 데이터를 담음 링크는 234, 223, 21로 정렬되고, 데이터가 들어오면, 차례대로 비교합니다.
노드는
typedef strunt _node
{
char number[10];
int len
strunt _node* next;
};
이렇게 구성하면 될것 같습니다.
감쏴합니다.

실력이 있으면 삶이 편하다... 영차 영차...

moonzoo의 이미지

굳이 정렬을 할 필요가 없을지도..

#include <stdio.h>

int main()
{
    char * token = "12345678";
    char * string[] = {"1","12345","123456","1234"};
    int     rt;
    int     num;

    num = sizeof(string) / sizeof(char *);

    rt = search_idx( string, num, token);

    printf("result=%s\n",string[rt]);

}

int search_idx( char * str[], int num, char * token)
{
    int select;
    int max;
    int i;
    int len;
    int rt;

    max = 0;
    select = -1;
    for( i = 0 ; i < num ; i++)
    {
        len = strlen( str[i] );
        rt  = memcmp( token, str[i], len);
        if( rt == 0 )
        {
            if( max < len )
            {
                max = len;
                select = i;
            }
        }

    }

    if( select < 0 ) return -1;

    return select;
}
익명 사용자의 이미지

딴지는 아닙니다.. 버그가 있군요 ㅡㅡa len..

정렬하고 버킷을 만드시는 이유는 데이터량이 많을경우

속도 때문에 그러시는것같은데요..

매번 순차검색하시는건 부담스러운 작업이라 그런게 아니신가 싶습니다..

익명 사용자의 이미지

Anonymous wrote:
딴지는 아닙니다.. 버그가 있군요 ㅡㅡa len..
quote]

어떤 버그가 있다는 건지 설명좀 해주세요..

생각해 보니 정렬을 해두는 것도 괜찮겠군요.

익명 사용자의 이미지

Anonymous wrote:
딴지는 아닙니다.. 버그가 있군요 ㅡㅡa len..
quote]

어떤 버그가 있다는 건지 설명좀 해주세요..

생각해 보니 정렬을 해두는 것도 괜찮겠군요.

moonzoo의 이미지

에고..로그인 안하고 글썼더니..

실수로 글 2개 올렸는데 삭제가 안되는 듯 --;

익명 사용자의 이미지

memcmp( token, str[i], num);

이부분 맞는부분인가요 num 은 길이는 아닌것같은데 해서

적어봤습니다.. 소스를 세세히 안보구 그냥 훌터보다가 그런거같아서.. ㅡㅡa

익명 사용자의 이미지

p.s 네 손님 편하긴한데.. 답글 잘못올리면 삭제가 안되는 안타까운점이 ㅡㅡa
요즘 로긴거의 안하는데.. 손님기능 장단점이 있는듯.. ^^;;

moonzoo의 이미지

Anonymous wrote:
memcmp( token, str[i], num);

이부분 맞는부분인가요 num 은 길이는 아닌것같은데 해서

적어봤습니다.. 소스를 세세히 안보구 그냥 훌터보다가 그런거같아서.. ㅡㅡa

아 맞습니다.. 수정했습니다^^

cedar의 이미지

Anonymous wrote:
오름차순으로 정렬한다는 문구는 오름차순을 매번 정렬한다는 의미가 아니었습니다만.. 자료구조자체를 항상 오름차순으로 유지를 해야한다는 의미였습니다..

자료구조 자체를 항상 오름차순으로 유지하려면, 트리를 사용하면 간단합니다.

다음 코드는 ANSI C++ STL의 multiset 컨테이너와 equal, find_if 알고리듬을 써서 작성해 본 것입니다.

//---------------------------------------------------------------------------
#include <iostream>
#include <string>
#pragma hdrstop
#include <algorithm>
#include <set>
#include <iterator>
#include <functional>
//---------------------------------------------------------------------------

template <class T>
inline void PrintElements(const T& c)
{
    using namespace std;
    copy(c.begin(), c.end(), ostream_iterator<string>(cout, " "));
    cout.put('\n');
}

template <class T, class U>
struct SizeGreater : public std::binary_function<T, U, bool>
{
    bool operator()(const T& x, const U& y)
    {
    	return x.size() > y.size();
    }
};


template <class T>
struct PartialMatch : public std::binary_function<T, T, bool>
{
    bool operator()(const T& x, const T& y)
    {
    	return std::equal(x.begin(), x.end(), y.begin());
    }
};


int main()
{
    using namespace std;

    multiset<string, SizeGreater<string, string> > set1, set2, set3;

    set1.insert("a");
    set1.insert("ab");
    set1.insert("acd");
    set1.insert("abc");
    cout << "set1: ";
    PrintElements(set1);

    set2.insert("a");
    set2.insert("abcde");
    set2.insert("abc");
    set2.insert("abcd");
    cout << "set2: ";
    PrintElements(set2);

    set3.insert("a");
    set3.insert("adb");
    set3.insert("adc");
    set3.insert("abch");
    cout << "set3: ";
    PrintElements(set3);

    cout << "\nMaximum match of set1 : " <<
    	*find_if(set1.begin(), set1.end(),
    		bind2nd(PartialMatch<string>(), "abcdefgh"));
    cout << "\nMaximum match of set2 : " <<
    	*find_if(set2.begin(), set2.end(),
    		bind2nd(PartialMatch<string>(), "abcdefgh"));
    cout << "\nMaximum match of set3 : " <<
    	*find_if(set3.begin(), set3.end(),
    		bind2nd(PartialMatch<string>(), "abcdefgh"));

    return 0;
}

실행 결과는 다음과 같습니다.

set1: acd abc ab a
set2: abcde abcd abc a
set3: abch adb adc a

Maximum match of set1 : abc
Maximum match of set2 : abcde
Maximum match of set3 : a

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.