Попытка сравнить пространственные сложности 2 алгоритмов сортировки.Не знаю, как интерпретировать ответ

Question

У меня есть 2 алгоритма сортировки, сортировка слиянием и сортировка вставкой.Я пытаюсь проверить, сколько оперативной памяти они выделяют во время выполнения, чтобы сделать сравнение.Оба сортируют массив из 1000 элементов, целые числа которых находятся в диапазоне от 0 до 999.

Программы скомпилированы в двоичный файл с именем main (merge_sort/main и insertion_sort/main).Итак, я запускаю:

memusage -T ./main

по обоим алгоритмам.

оба возвращают:

heap total: 73728, heap peak: 73728, stack peak: 6144

Почему они возвращают то же самое?Не должна ли сортировка слиянием выделять больше памяти, чем сортировка вставкой?Я даже использую memusage правильно?

Я также пытался проверить их с помощью Valgrind, который также возвращает то же самое для обоих:

==26544== HEAP SUMMARY:
==26544==     in use at exit: 0 bytes in 0 blocks
==26544==   total heap usage: 2 allocs, 2 frees, 73,728 bytes allocated

Моя теория: что либо я не знаю,что я делаю,

или что отсортированный список слишком мал.Поэтому использование памяти выглядит одинаково.

Код:

Сортировка слиянием

/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>
#include<time.h>

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    /* create temp arrays */
    int L[n1], R[n2];

    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy the remaining elements of L[], if there
    are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there
    are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {
        397, 326, 157, 581, 198, 158, 107, 479, 919, 288, 118, 14, 384, 389, 354, 905, 648, 24, 639, 279, 846, 896, 901, 491, 827, 502, 119, 520, 544, 688, 433, 542, 280, 834, 574, 739, 168, 714, 367, 547, 555, 616, 71, 583, 77, 372, 380, 414, 80, 828, 671, 900, 710, 852, 810, 471, 493, 832, 310, 579, 605, 174, 19, 576, 162, 695, 635, 851, 265, 48, 536, 228, 754, 300, 610, 272, 619, 825, 770, 147, 9, 813, 525, 135, 768, 654, 889, 446, 910, 678, 432, 172, 618, 41, 839, 589, 304, 484, 765, 357, 427, 617, 75, 683, 930, 593, 341, 149, 733, 27, 556, 474, 987, 156, 501, 665, 370, 523, 142, 420, 114, 798, 989, 382, 543, 879, 294, 305, 684, 331, 443, 383, 625, 647, 780, 811, 34, 621, 744, 842, 150, 938, 301, 495, 965, 392, 634, 358, 570, 789, 266, 242, 709, 278, 932, 57, 952, 475, 984, 136, 133, 637, 734, 207, 697, 362, 344, 332, 89, 529, 188, 164, 124, 317, 103, 257, 514, 364, 356, 203, 112, 831, 867, 644, 815, 452, 456, 260, 291, 90, 13, 21, 160, 217, 251, 459, 213, 110, 455, 56, 753, 127, 349, 884, 434, 982, 224, 410, 104, 540, 640, 973, 486, 945, 201, 166, 99, 535, 229, 725, 361, 483, 190, 743, 998, 409, 159, 102, 55, 219, 720, 33, 971, 859, 335, 887, 538, 363, 557, 696, 11, 951, 51, 845, 231, 723, 569, 63, 903, 185, 406, 505, 833, 309, 49, 599, 788, 511, 990, 196, 324, 803, 247, 970, 440, 504, 627, 205, 656, 308, 948, 690, 551, 819, 988, 608, 67, 519, 907, 510, 603, 256, 597, 880, 893, 214, 95, 270, 915, 179, 298, 378, 550, 953, 717, 321, 992, 863, 796, 868, 604, 152, 368, 15, 284, 17, 925, 808, 799, 841, 946, 974, 450, 546, 682, 91, 666, 402, 283, 736, 567, 679, 125, 299, 319, 762, 849, 785, 264, 797, 623, 401, 689, 140, 461, 171, 454, 624, 853, 724, 191, 130, 86, 451, 87, 109, 38, 61, 413, 348, 289, 829, 969, 670, 528, 588, 937, 766, 885, 237, 823, 592, 184, 73, 239, 643, 180, 10, 195, 277, 787, 431, 562, 390, 338, 146, 638, 85, 424, 652, 2, 631, 685, 405, 35, 387, 912, 333, 740, 692, 769, 66, 554, 565, 926, 223, 322, 826, 657, 858, 703, 1, 986, 312, 246, 31, 577, 323, 145, 439, 375, 39, 170, 106, 478, 978, 716, 254, 756, 37, 360, 350, 463, 269, 52, 64, 386, 509, 997, 429, 379, 655, 916, 878, 553, 794, 807, 197, 16, 840, 947, 860, 920, 963, 70, 183, 572, 763, 192, 729, 340, 238, 209, 469, 151, 167, 292, 303, 129, 847, 749, 4, 218, 216, 924, 215, 784, 243, 394, 836, 782, 476, 268, 78, 54, 590, 81, 908, 23, 704, 428, 778, 976, 680, 211, 622, 131, 273, 236, 487, 416, 767, 854, 870, 255, 837, 336, 611, 958, 233, 991, 3, 764, 83, 7, 541, 244, 792, 790, 0, 407, 418, 812, 334, 32, 872, 883, 537, 518, 72, 293, 886, 220, 866, 42, 730, 929, 891, 126, 470, 686, 329, 28, 568, 563, 659, 186, 706, 923, 497, 942, 844, 850, 492, 783, 715, 415, 153, 120, 448, 496, 468, 398, 620, 369, 373, 629, 79, 835, 711, 750, 311, 738, 346, 881, 121, 911, 50, 612, 498, 395, 955, 490, 774, 944, 506, 584, 664, 445, 173, 524, 561, 252, 713, 359, 771, 595, 96, 458, 956, 967, 422, 507, 177, 515, 342, 488, 759, 274, 275, 385, 816, 983, 306, 263, 830, 897, 760, 82, 426, 5, 698, 200, 981, 276, 559, 613, 154, 532, 735, 84, 345, 909, 94, 202, 302, 580, 508, 44, 134, 374, 898, 100, 993, 116, 712, 943, 646, 552, 975, 800, 6, 824, 328, 318, 960, 245, 708, 548, 403, 60, 931, 499, 676, 88, 894, 465, 921, 817, 693, 591, 957, 818, 721, 596, 649, 935, 261, 747, 391, 917, 314, 296, 460, 376, 412, 227, 240, 139, 871, 776, 691, 513, 93, 606, 531, 464, 694, 977, 108, 69, 259, 466, 417, 58, 737, 786, 43, 707, 933, 307, 74, 719, 653, 327, 746, 913, 262, 922, 731, 199, 494, 804, 877, 873, 732, 285, 727, 47, 210, 927, 914, 194, 758, 602, 582, 566, 941, 598, 809, 672, 966, 258, 137, 961, 902, 467, 92, 105, 316, 29, 234, 781, 675, 286, 226, 353, 857, 777, 472, 68, 985, 480, 330, 250, 248, 282, 962, 838, 176, 208, 40, 175, 178, 281, 396, 444, 436, 560, 521, 895, 366, 377, 586, 578, 212, 641, 232, 687, 571, 876, 585, 117, 101, 862, 701, 934, 939, 968, 189, 53, 677, 573, 869, 113, 642, 65, 607, 143, 979, 645, 856, 352, 20, 522, 249, 355, 148, 22, 473, 742, 98, 347, 419, 477, 705, 674, 757, 899, 430, 489, 425, 949, 726, 950, 123, 667, 399, 297, 594, 650, 587, 503, 141, 442, 748, 221, 775, 500, 339, 668, 400, 45, 814, 516, 663, 996, 772, 882, 230, 267, 722, 404, 821, 204, 755, 12, 702, 435, 822, 315, 630, 673, 848, 438, 482, 408, 928, 512, 371, 779, 626, 235, 527, 462, 904, 651, 661, 411, 752, 36, 980, 761, 485, 855, 241, 222, 287, 46, 802, 801, 206, 453, 111, 874, 295, 59, 628, 806, 290, 575, 600, 337, 728, 995, 138, 609, 875, 193, 30, 658, 558, 76, 481, 890, 745, 615, 132, 614, 795, 393, 351, 741, 564, 805, 457, 313, 545, 632, 964, 381, 25, 533, 26, 633, 62, 530, 751, 517, 936, 791, 820, 155, 940, 365, 843, 8, 918, 662, 225, 681, 388, 187, 660, 144, 793, 773, 181, 421, 161, 423, 447, 169, 994, 669, 700, 163, 526, 999, 959, 437, 449, 888, 271, 954, 18, 253, 320, 892, 864, 718, 865, 601, 699, 972, 549, 115, 441, 128, 861, 539, 165, 534, 325, 636, 122, 97, 182, 906, 343
    };
    int n = sizeof(arr)/sizeof(arr[0]);

    clock_t begin = clock();

    /* here, do your time-consuming job */
    mergeSort(arr, 0, n-1);

    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    printf("Merge: %.10f", time_spent);
    printf("\n");
    return 0;
}

Сортировка вставкой

// C program for insertion sort
#include <math.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /* Move elements of arr[0..i-1], that are
        greater than key, to one position ahead
        of their current position */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// A utility function to print an array of size n
void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

/* Driver program to test insertion sort */
int main()
{
    int arr[] = {
        397, 326, 157, 581, 198, 158, 107, 479, 919, 288, 118, 14, 384, 389, 354, 905, 648, 24, 639, 279, 846, 896, 901, 491, 827, 502, 119, 520, 544, 688, 433, 542, 280, 834, 574, 739, 168, 714, 367, 547, 555, 616, 71, 583, 77, 372, 380, 414, 80, 828, 671, 900, 710, 852, 810, 471, 493, 832, 310, 579, 605, 174, 19, 576, 162, 695, 635, 851, 265, 48, 536, 228, 754, 300, 610, 272, 619, 825, 770, 147, 9, 813, 525, 135, 768, 654, 889, 446, 910, 678, 432, 172, 618, 41, 839, 589, 304, 484, 765, 357, 427, 617, 75, 683, 930, 593, 341, 149, 733, 27, 556, 474, 987, 156, 501, 665, 370, 523, 142, 420, 114, 798, 989, 382, 543, 879, 294, 305, 684, 331, 443, 383, 625, 647, 780, 811, 34, 621, 744, 842, 150, 938, 301, 495, 965, 392, 634, 358, 570, 789, 266, 242, 709, 278, 932, 57, 952, 475, 984, 136, 133, 637, 734, 207, 697, 362, 344, 332, 89, 529, 188, 164, 124, 317, 103, 257, 514, 364, 356, 203, 112, 831, 867, 644, 815, 452, 456, 260, 291, 90, 13, 21, 160, 217, 251, 459, 213, 110, 455, 56, 753, 127, 349, 884, 434, 982, 224, 410, 104, 540, 640, 973, 486, 945, 201, 166, 99, 535, 229, 725, 361, 483, 190, 743, 998, 409, 159, 102, 55, 219, 720, 33, 971, 859, 335, 887, 538, 363, 557, 696, 11, 951, 51, 845, 231, 723, 569, 63, 903, 185, 406, 505, 833, 309, 49, 599, 788, 511, 990, 196, 324, 803, 247, 970, 440, 504, 627, 205, 656, 308, 948, 690, 551, 819, 988, 608, 67, 519, 907, 510, 603, 256, 597, 880, 893, 214, 95, 270, 915, 179, 298, 378, 550, 953, 717, 321, 992, 863, 796, 868, 604, 152, 368, 15, 284, 17, 925, 808, 799, 841, 946, 974, 450, 546, 682, 91, 666, 402, 283, 736, 567, 679, 125, 299, 319, 762, 849, 785, 264, 797, 623, 401, 689, 140, 461, 171, 454, 624, 853, 724, 191, 130, 86, 451, 87, 109, 38, 61, 413, 348, 289, 829, 969, 670, 528, 588, 937, 766, 885, 237, 823, 592, 184, 73, 239, 643, 180, 10, 195, 277, 787, 431, 562, 390, 338, 146, 638, 85, 424, 652, 2, 631, 685, 405, 35, 387, 912, 333, 740, 692, 769, 66, 554, 565, 926, 223, 322, 826, 657, 858, 703, 1, 986, 312, 246, 31, 577, 323, 145, 439, 375, 39, 170, 106, 478, 978, 716, 254, 756, 37, 360, 350, 463, 269, 52, 64, 386, 509, 997, 429, 379, 655, 916, 878, 553, 794, 807, 197, 16, 840, 947, 860, 920, 963, 70, 183, 572, 763, 192, 729, 340, 238, 209, 469, 151, 167, 292, 303, 129, 847, 749, 4, 218, 216, 924, 215, 784, 243, 394, 836, 782, 476, 268, 78, 54, 590, 81, 908, 23, 704, 428, 778, 976, 680, 211, 622, 131, 273, 236, 487, 416, 767, 854, 870, 255, 837, 336, 611, 958, 233, 991, 3, 764, 83, 7, 541, 244, 792, 790, 0, 407, 418, 812, 334, 32, 872, 883, 537, 518, 72, 293, 886, 220, 866, 42, 730, 929, 891, 126, 470, 686, 329, 28, 568, 563, 659, 186, 706, 923, 497, 942, 844, 850, 492, 783, 715, 415, 153, 120, 448, 496, 468, 398, 620, 369, 373, 629, 79, 835, 711, 750, 311, 738, 346, 881, 121, 911, 50, 612, 498, 395, 955, 490, 774, 944, 506, 584, 664, 445, 173, 524, 561, 252, 713, 359, 771, 595, 96, 458, 956, 967, 422, 507, 177, 515, 342, 488, 759, 274, 275, 385, 816, 983, 306, 263, 830, 897, 760, 82, 426, 5, 698, 200, 981, 276, 559, 613, 154, 532, 735, 84, 345, 909, 94, 202, 302, 580, 508, 44, 134, 374, 898, 100, 993, 116, 712, 943, 646, 552, 975, 800, 6, 824, 328, 318, 960, 245, 708, 548, 403, 60, 931, 499, 676, 88, 894, 465, 921, 817, 693, 591, 957, 818, 721, 596, 649, 935, 261, 747, 391, 917, 314, 296, 460, 376, 412, 227, 240, 139, 871, 776, 691, 513, 93, 606, 531, 464, 694, 977, 108, 69, 259, 466, 417, 58, 737, 786, 43, 707, 933, 307, 74, 719, 653, 327, 746, 913, 262, 922, 731, 199, 494, 804, 877, 873, 732, 285, 727, 47, 210, 927, 914, 194, 758, 602, 582, 566, 941, 598, 809, 672, 966, 258, 137, 961, 902, 467, 92, 105, 316, 29, 234, 781, 675, 286, 226, 353, 857, 777, 472, 68, 985, 480, 330, 250, 248, 282, 962, 838, 176, 208, 40, 175, 178, 281, 396, 444, 436, 560, 521, 895, 366, 377, 586, 578, 212, 641, 232, 687, 571, 876, 585, 117, 101, 862, 701, 934, 939, 968, 189, 53, 677, 573, 869, 113, 642, 65, 607, 143, 979, 645, 856, 352, 20, 522, 249, 355, 148, 22, 473, 742, 98, 347, 419, 477, 705, 674, 757, 899, 430, 489, 425, 949, 726, 950, 123, 667, 399, 297, 594, 650, 587, 503, 141, 442, 748, 221, 775, 500, 339, 668, 400, 45, 814, 516, 663, 996, 772, 882, 230, 267, 722, 404, 821, 204, 755, 12, 702, 435, 822, 315, 630, 673, 848, 438, 482, 408, 928, 512, 371, 779, 626, 235, 527, 462, 904, 651, 661, 411, 752, 36, 980, 761, 485, 855, 241, 222, 287, 46, 802, 801, 206, 453, 111, 874, 295, 59, 628, 806, 290, 575, 600, 337, 728, 995, 138, 609, 875, 193, 30, 658, 558, 76, 481, 890, 745, 615, 132, 614, 795, 393, 351, 741, 564, 805, 457, 313, 545, 632, 964, 381, 25, 533, 26, 633, 62, 530, 751, 517, 936, 791, 820, 155, 940, 365, 843, 8, 918, 662, 225, 681, 388, 187, 660, 144, 793, 773, 181, 421, 161, 423, 447, 169, 994, 669, 700, 163, 526, 999, 959, 437, 449, 888, 271, 954, 18, 253, 320, 892, 864, 718, 865, 601, 699, 972, 549, 115, 441, 128, 861, 539, 165, 534, 325, 636, 122, 97, 182, 906, 343,
    };

    int n = sizeof(arr)/sizeof(arr[0]);

    //printf("n: %d", n);
    //printf("Unsorted array: ");
    //printArray(arr, n);
    //printf("\n");
    clock_t begin = clock();

    /* here, do your time-consuming job */
    insertionSort(arr, n);

    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    //printf("Sorted array: ");
    //printArray(arr, n);
    //printf("\n");

    printf("Inser: %.10f", time_spent);
    printf("\n");



    return 0;
}

Answer 1

Результаты memusage и valgrind, о которых вы сообщаете, согласуются друг с другом: каждый показывает в общей сложности 73728 байт, которые динамически распределяются. И это тут же должно было дать вам паузу, потому что в ваших источниках нет вызовов динамических функций выделения памяти . Эти байты не относятся к вашим функциям сортировки; они должны возникать в результате распределения, выполняемого стандартной библиотекой в ​​ее коде установки или в одной из немногих библиотечных функций, которые вы вызываете.

Поскольку memusage и libmemusage.so, на которые он опирается, предоставляются glibc, никто не ожидал, что они сообщат о собственном использовании glibc, и, на самом деле, для меня они этого не делают. Я не могу объяснить, почему вы видите другой результат, но как дикое предположение, возможно, вы используете несовпадающие версии glibc и libmemusage.so.

НО, вы могли бы сказать, как насчет использования стека? Разве два подхода не должны использовать разное количество стеков? И не должны ли они использовать некоторый стек, а не 0, как сообщается в комментариях? Здесь вы должны понимать, что лежащий в основе libmemusage работает, оборачивая выбранные функции выделения памяти, а не все функции. Для memusage документов он вычисляет использование стека следующим образом:

Перед первым вызовом любой контролируемой функции указатель стека адрес (указатель базового стека) сохраняется. После каждого [отслеживаемого] вызова функции фактический адрес указателя стека читается и отличается от базового указатель стека вычисляется. Максимум этих различий тогда пик стека.

(Акцент добавлен). Таким образом,

1. memusage предоставляет только оценку использования стека, и эта оценка делается путем выборки указателя стека вокруг вызовов контролируемых функций.

2. Таким образом, для ваших конкретных программ memusage не сообщает ничего об использовании стека алгоритма сортировки, поскольку ваш код не вызывает вызовов отслеживаемых функций.

Вы можете обойти это, вручную установив свой код, чтобы libmemusage увидел использование его стека. Например, введите

free(malloc(0));

в начале main(), чтобы обеспечить запись нижней точки использования стека и вставлять вызовы в функцию, такую ​​как

void usage_instrumentation(void) {
    free(malloc(0));
}

в каждую из ваших других функций. Вызов функции должен использоваться в другом месте, кроме main, чтобы захватить использование стека вызывающей функции; malloc и free следует вызывать непосредственно в main для захвата нижней точки , исключая использование main, чтобы это использование было включено в окончательную оценку. Кроме того, скомпилируйте с отключенной функцией inlining (и, возможно, всеми оптимизациями), чтобы этот механизм не был побежден вашим компилятором.

Если я сделаю это, тогда для меня memusage сообщит о 4304 байтах стека для сортировки вставки и 8496 для сортировки слиянием, с разницей, немного превышающей размер вашего массива. Это так, как я и ожидал.