gpt4 book ai didi

将元素添加到固定长度数组并删除第一个元素的干净方法?

转载 作者:行者123 更新时间:2023-11-30 16:21:53 24 4
gpt4 key购买 nike

我需要一种干净的方法来向数组添加元素,如果数组“溢出”,则 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;
}

最佳答案

环形缓冲区解决方案和“随机缓冲区”解决方案都不是特别复杂。这是每一个。请注意,环形缓冲区解决方案在 16 个数组中存储 15 个值;洗牌缓冲区解决方案使用大小为 15 的数组。如果将 (1: 30) 等条目映射到 (99: 30),这些解决方案会提供相同的输出序列> 允许数据存储方式的差异。

这两种解决方案都假设您了解结构(以及指向结构的指针)。

随机播放缓冲区

这与问题中的代码最接近。

#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;
}

环形缓冲区

#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 的情况下,主程序中循环 100 万次对于环形缓冲区需要 4.5 毫秒,而对于随机缓冲区则需要 9.0 毫秒。将缓冲区大小更改为 2047 或 2048,环形缓冲区的时间为 3.7 毫秒,而随机缓冲区的时间为 87.3 毫秒。启用打印后,环形缓冲区在打印中完成的轻微额外工作淹没了不洗牌带来的性能增益;这两个程序的运行时间基本相同:4,546.5 毫秒 vs 4,477.2 毫秒(因此,在启用打印的情况下,洗牌缓冲区的速度稍快一些 — 很大程度上是因为它仅生成 353 MiB 的数据,而环形缓冲区生成 368 MiB 的数据 —随着计时运行,数据被写入 /dev/null)。

测量的时间是可执行文件的运行时间,而不是 CPU 时间本身。测试使用配备 2.9 GHz Intel Core i7、16 GiB 2133 MHz LPDDR3 RAM 的 15 英寸 MacBook Pro(2017 年),运行 macOS 10.14.3 Mojave 并使用自制的 GCC 8.2.0。速度测试为困难 - 我认为没有打印的结果是有意义的,但是 YMMV 。如果您需要演示“打印很慢”,这很可能是一个不错的选择。

关于将元素添加到固定长度数组并删除第一个元素的干净方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54680129/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com