Чистый способ добавить элементы в массив фиксированной длины и удалить первый элемент? - PullRequest
Новая
       1

Чистый способ добавить элементы в массив фиксированной длины и удалить первый элемент?

0 голосов
/ 14 февраля 2019

Мне нужен чистый способ добавления элементов в массив, и если массив «переполняется», то элемент в 0 должен быть заменен элементом в 1 и т. Д., Пока не освободится место для нового элемента.

Вот пример (псевдокод): 

array = [0, 0, 0, 0, 0]
// elements get added
array = [1, 0, 0, 0, 0]
...
array = [1, 2, 3, 4, 5]
// Array is full!
// Another elements gets added
array = [2, 3, 4, 5, 6]
// And so on..

Я попытался сделать это на онлайн-компиляторе, но с треском провалился, и вот код: 

int main()
{
    int arr[10] = { 555, 555, 555, 555, 555, 555, 555, 555, 555, 555 };

    for (int i = 0; i < 100; i++)
    {
        int arr_idx = i % 10;

        if (arr[10] != 555)
        {
            if (arr_idx < 9)
            {
                arr[arr_idx] = arr[arr_idx + 1];
            }
            else
            {
                arr[arr_idx] = 0;
            }
        }
        else
        {
            arr[arr_idx] = i;
            printf("arr: %d", arr[arr_idx]);
        }

        printf("---\n");
        for (int j = 0; j < 10; j++)
        {
            printf("[%d]Arr = %d\n", j, arr[j]);
        }
    }
    return 0;
}

1 Ответ

0 голосов
/ 14 февраля 2019

Ни решение с кольцевым буфером, ни решение с "тасующим буфером" не являются особенно сложнымиВот один из каждого.Обратите внимание, что решение кольцевого буфера хранит 15 значений в массиве из 16;решение с буфером случайных чисел использует массив размером 15. Решения дают одинаковую последовательность выходных данных, если сопоставить записи, такие как ( 1: 30) с (99: 30), чтобы учесть различия в способе хранения данных.

Оба решения предполагают, что вы понимаете структуры (и указатели на структуры тоже).

Shuffle Buffer

Это наиболее близко соответствует коду в вопросе. 

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

enum { SB_SIZE = 15 };

typedef int Data;
#define DATA_PRI_FMT "d"

struct ShuffleBuffer
{
   size_t sb_last;
   Data   sb_data[SB_SIZE];
};
typedef struct ShuffleBuffer ShuffleBuffer;

static inline void sb_shuffle(ShuffleBuffer *sbp)
{
    if (sbp->sb_last > 0)
    {
        memmove(sbp->sb_data, sbp->sb_data + 1, (SB_SIZE - 1) * sizeof(sbp->sb_data[0]));
        sbp->sb_last--;
    }
}

static void sb_insert(ShuffleBuffer *sbp, Data value)
{
    if (sbp->sb_last == SB_SIZE)
        sb_shuffle(sbp);
    sbp->sb_data[sbp->sb_last++] = value;
}

static bool sb_remove(ShuffleBuffer *sbp, Data *valuep)
{
    if (sbp->sb_last == 0)
        return false;
    *valuep = sbp->sb_data[0];
    sb_shuffle(sbp);
    return true;
}

static void sb_print(const char *tag, const ShuffleBuffer *sbp)
{
    printf("%s: (last = %zu)\n", tag, sbp->sb_last);
    int nbytes = 0;
    const char *pad = "";
    for (size_t i = 0; i < sbp->sb_last; i++)
    {
        nbytes += printf("%s(%2zu: %3" DATA_PRI_FMT ")", pad, i, sbp->sb_data[i]);
        if (nbytes > 40)
        {
            putchar('\n');
            nbytes = 0;
            pad = "";
        }
        else
            pad = " ";
    }
    if (nbytes != 0)
        putchar('\n');
}

int main(void)
{
    ShuffleBuffer rb = { 0, { 0 } };

    for (Data i = 0; i < 100; i++)
    {
        sb_insert(&rb, i * 7 + 23);
        sb_print("Post insert", &rb);
        if ((i & 1) == 1)
        {
            Data value;
            if (sb_remove(&rb, &value))
                printf("Value %" DATA_PRI_FMT " removed\n", value);
            else
                sb_print("Ring Buffer Empty", &rb);
        sb_print("Post remove", &rb);
        }
    }

    printf("Insert/remove loop over\n");

    Data value;
    while (sb_remove(&rb, &value))
        printf("Value %" DATA_PRI_FMT " removed\n", value);

    return 0;
}

Ring Buffer 

#include <stdbool.h>
#include <stdio.h>

enum { RB_SIZE = 16 };

typedef int Data;
#define DATA_PRI_FMT "d"

struct RingBuffer
{
   size_t rb_head;
   size_t rb_tail;
   Data   rb_data[RB_SIZE];
};
typedef struct RingBuffer RingBuffer;

static inline size_t rb_nextpos(size_t pos)
{
    return (pos + 1) % RB_SIZE;
}

static void rb_insert(RingBuffer *rbp, Data value)
{
    rbp->rb_data[rbp->rb_head] = value;
    rbp->rb_head = rb_nextpos(rbp->rb_head);
    if (rbp->rb_tail == rbp->rb_head)
        rbp->rb_tail = rb_nextpos(rbp->rb_tail);
}

static bool rb_remove(RingBuffer *rbp, Data *valuep)
{
    if (rbp->rb_head == rbp->rb_tail)
        return false;
    *valuep = rbp->rb_data[rbp->rb_tail];
    rbp->rb_tail = rb_nextpos(rbp->rb_tail);
    return true;
}

static void rb_print(const char *tag, const RingBuffer *rbp)
{
    printf("%s: (head = %zu, tail = %zu)\n", tag, rbp->rb_head, rbp->rb_tail);
    int nbytes = 0;
    const char *pad = "";
    for (size_t i = rbp->rb_tail; i != rbp->rb_head; i = rb_nextpos(i))
    {
        nbytes += printf("%s(%2zu: %3" DATA_PRI_FMT ")", pad, i, rbp->rb_data[i]);
        if (nbytes > 40)
        {
            putchar('\n');
            nbytes = 0;
            pad = "";
        }
        else
            pad = " ";
    }
    if (nbytes != 0)
        putchar('\n');
}

int main(void)
{
    RingBuffer rb = { 0, 0, { 0 } };

    for (Data i = 0; i < 100; i++)
    {
        rb_insert(&rb, i * 7 + 23);
        rb_print("Post insert", &rb);
        if ((i & 1) == 1)
        {
            Data value;
            if (rb_remove(&rb, &value))
                printf("Value %" DATA_PRI_FMT " removed\n", value);
            else
                rb_print("Ring Buffer Empty", &rb);
        rb_print("Post remove", &rb);
        }
    }

    printf("Insert/remove loop over\n");

    Data value;
    while (rb_remove(&rb, &value))
        printf("Value %" DATA_PRI_FMT " removed\n", value);

    return 0;
}

Если ваш компилятор настолько устарел, что не распознает inline в качестве ключевого слова, просто добавьте #define inline /* C99 not available */ в верхней части файла (или, лучше, получите компиляторкоторый распознает почти 20-летний стандарт).

Пример вывода из кольцевого буфера 

Post insert: (head = 1, tail = 0)
( 0:  23)
Post insert: (head = 2, tail = 0)
( 0:  23) ( 1:  30)
Value 23 removed
Post remove: (head = 2, tail = 1)
( 1:  30)
Post insert: (head = 3, tail = 1)
( 1:  30) ( 2:  37)
Post insert: (head = 4, tail = 1)
( 1:  30) ( 2:  37) ( 3:  44)
Value 30 removed
Post remove: (head = 4, tail = 2)
( 2:  37) ( 3:  44)
Post insert: (head = 5, tail = 2)
( 2:  37) ( 3:  44) ( 4:  51)
Post insert: (head = 6, tail = 2)
( 2:  37) ( 3:  44) ( 4:  51) ( 5:  58)
Value 37 removed
Post remove: (head = 6, tail = 3)
( 3:  44) ( 4:  51) ( 5:  58)
Post insert: (head = 7, tail = 3)
( 3:  44) ( 4:  51) ( 5:  58) ( 6:  65)
Post insert: (head = 8, tail = 3)
( 3:  44) ( 4:  51) ( 5:  58) ( 6:  65) ( 7:  72)
Value 44 removed
Post remove: (head = 8, tail = 4)
( 4:  51) ( 5:  58) ( 6:  65) ( 7:  72)
Post insert: (head = 9, tail = 4)
( 4:  51) ( 5:  58) ( 6:  65) ( 7:  72) ( 8:  79)
Post insert: (head = 10, tail = 4)
( 4:  51) ( 5:  58) ( 6:  65) ( 7:  72) ( 8:  79)
( 9:  86)
Value 51 removed
Post remove: (head = 10, tail = 5)
( 5:  58) ( 6:  65) ( 7:  72) ( 8:  79) ( 9:  86)
Post insert: (head = 11, tail = 5)
( 5:  58) ( 6:  65) ( 7:  72) ( 8:  79) ( 9:  86)
(10:  93)
Post insert: (head = 12, tail = 5)
( 5:  58) ( 6:  65) ( 7:  72) ( 8:  79) ( 9:  86)
(10:  93) (11: 100)
Value 58 removed
Post remove: (head = 12, tail = 6)
( 6:  65) ( 7:  72) ( 8:  79) ( 9:  86) (10:  93)
(11: 100)
Post insert: (head = 13, tail = 6)
( 6:  65) ( 7:  72) ( 8:  79) ( 9:  86) (10:  93)
(11: 100) (12: 107)
Post insert: (head = 14, tail = 6)
( 6:  65) ( 7:  72) ( 8:  79) ( 9:  86) (10:  93)
(11: 100) (12: 107) (13: 114)
Value 65 removed
Post remove: (head = 14, tail = 7)
( 7:  72) ( 8:  79) ( 9:  86) (10:  93) (11: 100)
(12: 107) (13: 114)
Post insert: (head = 15, tail = 7)
( 7:  72) ( 8:  79) ( 9:  86) (10:  93) (11: 100)
(12: 107) (13: 114) (14: 121)
Post insert: (head = 0, tail = 7)
( 7:  72) ( 8:  79) ( 9:  86) (10:  93) (11: 100)
(12: 107) (13: 114) (14: 121) (15: 128)
Value 72 removed
Post remove: (head = 0, tail = 8)
( 8:  79) ( 9:  86) (10:  93) (11: 100) (12: 107)
(13: 114) (14: 121) (15: 128)
Post insert: (head = 1, tail = 8)
( 8:  79) ( 9:  86) (10:  93) (11: 100) (12: 107)
(13: 114) (14: 121) (15: 128) ( 0: 135)
Post insert: (head = 2, tail = 8)
( 8:  79) ( 9:  86) (10:  93) (11: 100) (12: 107)
(13: 114) (14: 121) (15: 128) ( 0: 135) ( 1: 142)
Value 79 removed
Post remove: (head = 2, tail = 9)
( 9:  86) (10:  93) (11: 100) (12: 107) (13: 114)
(14: 121) (15: 128) ( 0: 135) ( 1: 142)
Post insert: (head = 3, tail = 9)
( 9:  86) (10:  93) (11: 100) (12: 107) (13: 114)
(14: 121) (15: 128) ( 0: 135) ( 1: 142) ( 2: 149)
Post insert: (head = 4, tail = 9)
( 9:  86) (10:  93) (11: 100) (12: 107) (13: 114)
(14: 121) (15: 128) ( 0: 135) ( 1: 142) ( 2: 149)
( 3: 156)
Value 86 removed
Post remove: (head = 4, tail = 10)
(10:  93) (11: 100) (12: 107) (13: 114) (14: 121)
(15: 128) ( 0: 135) ( 1: 142) ( 2: 149) ( 3: 156)
Post insert: (head = 5, tail = 10)
(10:  93) (11: 100) (12: 107) (13: 114) (14: 121)
(15: 128) ( 0: 135) ( 1: 142) ( 2: 149) ( 3: 156)
( 4: 163)
Post insert: (head = 6, tail = 10)
(10:  93) (11: 100) (12: 107) (13: 114) (14: 121)
(15: 128) ( 0: 135) ( 1: 142) ( 2: 149) ( 3: 156)
( 4: 163) ( 5: 170)
Value 93 removed
Post remove: (head = 6, tail = 11)
(11: 100) (12: 107) (13: 114) (14: 121) (15: 128)
( 0: 135) ( 1: 142) ( 2: 149) ( 3: 156) ( 4: 163)
( 5: 170)
Post insert: (head = 7, tail = 11)
(11: 100) (12: 107) (13: 114) (14: 121) (15: 128)
( 0: 135) ( 1: 142) ( 2: 149) ( 3: 156) ( 4: 163)
( 5: 170) ( 6: 177)
Post insert: (head = 8, tail = 11)
(11: 100) (12: 107) (13: 114) (14: 121) (15: 128)
( 0: 135) ( 1: 142) ( 2: 149) ( 3: 156) ( 4: 163)
( 5: 170) ( 6: 177) ( 7: 184)
Value 100 removed
Post remove: (head = 8, tail = 12)
(12: 107) (13: 114) (14: 121) (15: 128) ( 0: 135)
( 1: 142) ( 2: 149) ( 3: 156) ( 4: 163) ( 5: 170)
( 6: 177) ( 7: 184)
Post insert: (head = 9, tail = 12)
(12: 107) (13: 114) (14: 121) (15: 128) ( 0: 135)
( 1: 142) ( 2: 149) ( 3: 156) ( 4: 163) ( 5: 170)
( 6: 177) ( 7: 184) ( 8: 191)
Post insert: (head = 10, tail = 12)
(12: 107) (13: 114) (14: 121) (15: 128) ( 0: 135)
( 1: 142) ( 2: 149) ( 3: 156) ( 4: 163) ( 5: 170)
( 6: 177) ( 7: 184) ( 8: 191) ( 9: 198)
Value 107 removed
Post remove: (head = 10, tail = 13)
(13: 114) (14: 121) (15: 128) ( 0: 135) ( 1: 142)
( 2: 149) ( 3: 156) ( 4: 163) ( 5: 170) ( 6: 177)
( 7: 184) ( 8: 191) ( 9: 198)
Post insert: (head = 11, tail = 13)
(13: 114) (14: 121) (15: 128) ( 0: 135) ( 1: 142)
( 2: 149) ( 3: 156) ( 4: 163) ( 5: 170) ( 6: 177)
( 7: 184) ( 8: 191) ( 9: 198) (10: 205)
Post insert: (head = 12, tail = 13)
(13: 114) (14: 121) (15: 128) ( 0: 135) ( 1: 142)
( 2: 149) ( 3: 156) ( 4: 163) ( 5: 170) ( 6: 177)
( 7: 184) ( 8: 191) ( 9: 198) (10: 205) (11: 212)
Value 114 removed
Post remove: (head = 12, tail = 14)
(14: 121) (15: 128) ( 0: 135) ( 1: 142) ( 2: 149)
( 3: 156) ( 4: 163) ( 5: 170) ( 6: 177) ( 7: 184)
( 8: 191) ( 9: 198) (10: 205) (11: 212)
Post insert: (head = 13, tail = 14)
(14: 121) (15: 128) ( 0: 135) ( 1: 142) ( 2: 149)
( 3: 156) ( 4: 163) ( 5: 170) ( 6: 177) ( 7: 184)
( 8: 191) ( 9: 198) (10: 205) (11: 212) (12: 219)
Post insert: (head = 14, tail = 15)
(15: 128) ( 0: 135) ( 1: 142) ( 2: 149) ( 3: 156)
( 4: 163) ( 5: 170) ( 6: 177) ( 7: 184) ( 8: 191)
( 9: 198) (10: 205) (11: 212) (12: 219) (13: 226)
Value 128 removed
Post remove: (head = 14, tail = 0)
( 0: 135) ( 1: 142) ( 2: 149) ( 3: 156) ( 4: 163)
( 5: 170) ( 6: 177) ( 7: 184) ( 8: 191) ( 9: 198)
(10: 205) (11: 212) (12: 219) (13: 226)
Post insert: (head = 15, tail = 0)
( 0: 135) ( 1: 142) ( 2: 149) ( 3: 156) ( 4: 163)
( 5: 170) ( 6: 177) ( 7: 184) ( 8: 191) ( 9: 198)
(10: 205) (11: 212) (12: 219) (13: 226) (14: 233)
Post insert: (head = 0, tail = 1)
( 1: 142) ( 2: 149) ( 3: 156) ( 4: 163) ( 5: 170)
( 6: 177) ( 7: 184) ( 8: 191) ( 9: 198) (10: 205)
(11: 212) (12: 219) (13: 226) (14: 233) (15: 240)
Value 142 removed
Post remove: (head = 0, tail = 2)
( 2: 149) ( 3: 156) ( 4: 163) ( 5: 170) ( 6: 177)
( 7: 184) ( 8: 191) ( 9: 198) (10: 205) (11: 212)
(12: 219) (13: 226) (14: 233) (15: 240)
Post insert: (head = 1, tail = 2)
( 2: 149) ( 3: 156) ( 4: 163) ( 5: 170) ( 6: 177)
( 7: 184) ( 8: 191) ( 9: 198) (10: 205) (11: 212)
(12: 219) (13: 226) (14: 233) (15: 240) ( 0: 247)
…
Post insert: (head = 3, tail = 4)
( 4: 611) ( 5: 618) ( 6: 625) ( 7: 632) ( 8: 639)
( 9: 646) (10: 653) (11: 660) (12: 667) (13: 674)
(14: 681) (15: 688) ( 0: 695) ( 1: 702) ( 2: 709)
Post insert: (head = 4, tail = 5)
( 5: 618) ( 6: 625) ( 7: 632) ( 8: 639) ( 9: 646)
(10: 653) (11: 660) (12: 667) (13: 674) (14: 681)
(15: 688) ( 0: 695) ( 1: 702) ( 2: 709) ( 3: 716)
Value 618 removed
Post remove: (head = 4, tail = 6)
( 6: 625) ( 7: 632) ( 8: 639) ( 9: 646) (10: 653)
(11: 660) (12: 667) (13: 674) (14: 681) (15: 688)
( 0: 695) ( 1: 702) ( 2: 709) ( 3: 716)
Insert/remove loop over
Value 625 removed
Value 632 removed
Value 639 removed
Value 646 removed
Value 653 removed
Value 660 removed
Value 667 removed
Value 674 removed
Value 681 removed
Value 688 removed
Value 695 removed
Value 702 removed
Value 709 removed
Value 716 removed

Синхронизация

С повторением основного цикла 100 раз, на самом деле нетощутимая разница между двумя программами, если вы отключили печать, и она едва измеряется и не совсем надежна, если вы включаете печать.

При отключенной печатии размер буфера 15 или 16, цикл в миллион раз в основной программе занял 4,5 мс для кольцевого буфера против 9,0 мс для случайного буфера.Измените размер буфера на 2047 или 2048, и время было 3,7 мс для кольцевого буфера против 87,3 мс для случайного буфера.При включенной печати небольшая дополнительная работа, выполняемая кольцевым буфером при печати, сводила на нет прирост производительности из-за отсутствия перемешивания;две программы работали в одно и то же время: 4546,5 мс против 4 477,2 мс (таким образом, буфер перемешивания был немного быстрее при включенной печати - в значительной степени потому, что он генерировал только 353 МБ данных по сравнению с 368 МБ данных из кольцевого буфера -с записью данных в /dev/null с запусками синхронизации).

Измеренное время - это истекшее время выполнения для исполняемого файла, а не процессорное время как таковое.Тестирование проводилось для 15-дюймового MacBook Pro (2017 г.) с процессором Intel Core i7 с частотой 2,9 ГГц и 16 ГБ оперативной памяти с частотой 2133 МГц LPDDR3 , работающего под управлением MacOS 10.14.3 Mojave и использующего самодельный GCC 8.2.0.Скоростное тестирование сложно - я думаю, что результаты без печати значимы, но YMMV . Если вам когда-либо требовалось продемонстрировать, что «печать идет медленно», это вполне возможно, хороший.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...