هل هناك طريقة سهلة لفرز مجموعة من char*'s ؟سي ++

Question

لقد حصلت على مجموعة من char* في ملف.الشركة التي أعمل بها تقوم بتخزين البيانات في ملفات مسطحة..في بعض الأحيان يتم فرز البيانات، ولكن في بعض الأحيان لا يتم ذلك.أرغب في فرز البيانات الموجودة في الملفات.

الآن يمكنني كتابة الكود للقيام بذلك، من الصفر.هل توجد طريقة أسهل؟

بالطبع سيكون الفرز في المكان هو الخيار الأفضل.أنا أعمل على ملفات كبيرة ولدي ذاكرة وصول عشوائي قليلة.لكنني سأفكر في جميع الخيارات.

جميع السلاسل هي نفس الطول.

هذه بعض نماذج البيانات:

the data is of fixed length
the Data is of fixed length
thIS data is of fixed lengt

وهذا من شأنه أن يمثل ثلاثة سجلات بطول 28.التطبيق يعرف الطول.ينتهي كل سجل بـ CRLF (\r\n)، على الرغم من أنه لا ينبغي أن يهم لهذا النوع.

Answer 1

template<size_t length> int less(const char* left, const char* right) {
    return memcmp(left, right, length) < 0;
}

std::sort(array, array + array_length, less<buffer_length>);

Answer 2

استخدم برنامج نوع GNU (خارجيا) إذا لم تتمكن من احتواء البيانات إلى ذاكرة الوصول العشوائي: أنها ملفات الحجم سوف التعسفية نوع وأكبر الملف، أصغر تكلفة إضافية لخلق عملية

Answer 3

ويمكنك استخدام خوارزميات في STL على صفائف أنواع البيانات الأم، وليس فقط على حاويات STL. واقتراح آخر لاستخدام الأمراض المنقولة جنسيا :: ونوع لا تعمل كما شارك ومع ذلك، لأن strcmp إرجاع قيمة يتم تقييمها إلى ينطبق على جميع المقارنات عندما السلاسل ليست هي نفسها، وليس فقط إذا كان الجانب الأيسر أقل من الحق الجانب - وهو ما يريد الأمراض المنقولة جنسيا :: نوع. المسند ثنائي عودته صحيح من الجانب اليد اليسرى أقل من الجهة اليمنى.

وهذا يعمل:

struct string_lt : public std::binary_function<bool, char, char>
{
    bool operator()(const char* lhs, const char* rhs)
    {
        int ret = strcmp(lhs, rhs);
        return ret < 0;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    char* strings [] = {"Hello", "World", "Alpha", "Beta", "Omega"};
    size_t numStrings = sizeof(strings)/sizeof(strings[0]);

    std::sort(&strings[0], &strings[numStrings], string_lt());

    return 0;
}

Answer 4

وboost::bind تستطيع ان تفعل ذلك:

// ascending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) < 0); 

// descending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) > 0); 

تعديل : في السلاسل ليست خالية إنهاء:

// ascending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) < 0); 

// descending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) > 0); 

Answer 5

وربما كان أسهل طريقة هي استخدام القديم stdlib.h وظيفة qsort. هذا يجب أن تعمل:

qsort( array, num_elements, sizeof( char* ), strcmp )

يرجى ملاحظة أن هذا هو المعيار C ويعمل موثوق بها مع النص الإنجليزية فقط.

إذا كان لديك قائمة الكائنات سلسلة، ثم أشياء أخرى ممكنة في C ++.

إذا كنت على لينكس وكتابة جتك أو تطبيق كيو تي ثم أود أن أقترح أن يكون لديك نظرة على هذه المكتبات مسبقا.

Answer 6

إذا كانت الملفات الكبيرة ولا تناسب في RAM، يمكنك استخدام بن / دلو نوع لتقسيم البيانات إلى ملفات أصغر، وأخيرا تجميع القطع في ملف النتيجة. ردود أخرى تظهر لك كيفية فرز كل ملف دلو الفردية.

Answer 7

والطريقة الكنسي لفرز مجموعة من سلاسل الأحرف في C، وبالتالي فهو متاح ولكن لا ينصح بالضرورة طريقة للقيام بذلك في C ++، يستخدم مستوى indirection إلى strcmp():

static int qsort_strcmp(const void *v1, const void *v2)
{
    const char *s1 = *(char * const *)v1;
    const char *s2 = *(char * const *)v2;
    return(strcmp(s1, s2));
}

static void somefunc(void)   // Or omit the parameter altogether in C++
{
    char **array = ...assignment...
    size_t num_in_array = ...number of char pointers in array...
    ...
    qsort(array, num_in_array, sizeof(char *), qsort_strcmp);
    ...more code...
}

Answer 8

هناك عدد قليل من الأشياء تتبادر إلى الذهن:

1. إذا كانت بياناتك كبيرة جدًا بحيث لا يمكن احتواؤها في الذاكرة، فقد تحتاج فقط إلى إنشاء فهرس في الذاكرة لإزاحات الملفات، ثم تعيين الملف في الذاكرة للوصول إلى السلاسل (يعتمد على نظام التشغيل لديك).
2. في المكان سوف يتطلب أ كثير من نسخ الذاكرة.إذا كنت تستطيع، استخدم نوع الصدفة.وبعد ذلك، بمجرد معرفة الترتيب النهائي، يصبح من الأسهل إعادة ترتيب السلاسل في مكانها في الزمن الخطي.
3. إذا كانت جميع الأوتار بنفس الطول، فأنت حقًا تريد نوع الجذر.إذا لم تكن على دراية بالفرز الجذري، فإليك الفكرة الأساسية:الفرز القائم على المقارنة (وهو ما std::sort, qsort, ، وأي فرز آخر للأغراض العامة) يتطلب دائمًا وقت O(N log N).يقارن الفرز الجذري رقمًا واحدًا في كل مرة (بدءًا من str[0] وتنتهي عند str[K-1] لسلسلة K-lenth)، وبشكل عام يمكن أن يتطلب وقت O(N) فقط للتنفيذ.

استشر الإنترنت للحصول على وصف تفصيلي أفضل بكثير لخوارزميات فرز الجذر مما يمكنني تقديمه.وبصرف النظر عما قلته، فإنني سأتجنب كل الحلول الأخرى التي تستخدم مرافق الفرز المكتبية القياسية.إنهم فقط لم يصمموا مشكلتك الخاصة، لسوء الحظ.

Answer 9

وربما كنت ترغب في النظر في ملفات الذاكرة المعنونة (انظر HTTP: //en.wikipedia. غزاله / ويكي / الذاكرة-mapped_file )، وظيفة mmap () ( HTTP: // داخلي. wikipedia.org/wiki/Mmap ) على أنظمة تشغيل POSIX-شكوى. عليك أساسا الحصول على مؤشر إلى الذاكرة القريبة تمثل محتويات الملف.

والجانب الجيد هو أن نظام التشغيل سوف تأخذ الرعاية من أجزاء تحميل الملف إلى الذاكرة والتفريغ لهم مرة أخرى، حسب الحاجة.

واحد السلبي هو أنك سوف تحتاج إلى حل لشكل من أشكال ملف تأمين لتجنب الفساد إذا من المرجح أن الوصول إلى ملف عملية أكثر من واحد.

والجانب السلبي الآخر هو أن هذا لا يضمن الأداء الجيد - للقيام بذلك، عليك ان تحصل على خوارزمية الفرز الذي يحاول تجنب باستمرار تحميل وتفريغ الصفحات (ما لم يكن بالطبع لديك ذاكرة كافية لتحميل الملف بأكمله في الذاكرة ).

والأمل وقد أعطى هذا لك بعض الأفكار!