From 6ea6f9c1c60c7025e0b7bdc95a5d5aa395eedfbc Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Thu, 20 Oct 2022 00:33:23 -0400 Subject: Rename to SDC --- README.md | 14 ++++---- cd.c | 111 -------------------------------------------------------------- sd.c | 111 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 118 insertions(+), 118 deletions(-) delete mode 100644 cd.c create mode 100644 sd.c diff --git a/README.md b/README.md index 6a8af2a..360f429 100644 --- a/README.md +++ b/README.md @@ -1,25 +1,25 @@ -# CD +# SDC -C port of [SD](https://git.exozy.me/Ta180m/SD), a very efficient flash cards app +C port of [SD](https://git.exozy.me/a/SD), a very efficient flash cards app ## Usage Flash cards are stored in the `cards` table of a SQLite database. There are four columns: `idx INTEGER PRIMARY KEY, weight INTEGER, key STRING, val STRING`. The `idx` is a unique index for each card, starting at 0. The weight is how often the card should come up. The key and value are the front and reverse sides of the card. You can use the `sqlite3` CLI to create a card deck. -Now build this project with `gcc cd.c segmenttree.c -o cd -lsqlite3 -O2 -march=native` and run `./cd` to enjoy a fast flash cards experience! The program will display the `key` of a randomly selected card. Press any key to show the `val` of the card. Now press either `y` or `n` depending on whether you got the card correct, and the program adjusts that card's weight. +Now build this project with `gcc sd.c segmenttree.c -o sd -lsqlite3 -O2 -march=native` and run `./sd` to enjoy a fast flash cards experience! The program will display the `key` of a randomly selected card. Press any key to show the `val` of the card. Now press either `y` or `n` depending on whether you got the card correct, and the program adjusts that card's weight. -If you're wondering where the name came from, this is the C port of [SD](https://git.exozy.me/Ta180m/SD). +If you're wondering where the name came from, this is the C port of [SD](https://git.exozy.me/a/SD), which was named after a common type of flash card. 😀 ## Performance -CD is designed to be extremely efficient in order to support a very large number of flash cards and should be able to handle millions of cards with ease. If `N` is the number of cards, initializing the program requires `O(N)` time and `O(N)` memory. Selecting a random card and adjusting its weight requires `O(log N)` time. Internally CD uses [segment trees](https://en.wikipedia.org/wiki/Segment_tree) to achieve this time complexity. +SD is designed to be extremely efficient in order to support a very large number of flash cards and should be able to handle millions of cards with ease. If `N` is the number of cards, initializing the program requires `O(N)` time and `O(N)` memory. Selecting a random card and adjusting its weight requires `O(log N)` time. Internally SD uses [segment trees](https://en.wikipedia.org/wiki/Segment_tree) to achieve this time complexity. Some benchmark results using 10 card updates: ``` -Benchmark 1: ./cd < test +C version: ./sd < test Time (mean ± σ): 57.4 ms ± 4.5 ms [User: 6.9 ms, System: 2.4 ms] Range (min … max): 51.9 ms … 70.9 ms 41 runs -Benchmark 2: ./sd < test +Go version: ./sd < test Time (mean ± σ): 92.7 ms ± 6.8 ms [User: 8.4 ms, System: 4.5 ms] Range (min … max): 79.4 ms … 108.9 ms 33 runs ``` diff --git a/cd.c b/cd.c deleted file mode 100644 index 21caa57..0000000 --- a/cd.c +++ /dev/null @@ -1,111 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include "segmenttree.h" - -int main(int argc, char* argv[]) { - char *file = "cards"; - bool verbose = false; - - /* Proccess args */ - static struct option long_options[] = { - {"file", required_argument, NULL, 'f'}, - {"verbose", no_argument, NULL, 'v'} - }; - while (1) { - int option_index = 0; - int c = getopt_long(argc, argv, "f:v", long_options, &option_index); - if (c == -1) break; - switch (c) { - case 'f': file = strdup(optarg); break; - case 'v': verbose = true; break; - default: abort(); - } - } - - /* Seed the RNG */ - srand(time(0)); - - /* Connect to db */ - sqlite3 *db; - sqlite3_open(file, &db); - - /* Get number of cards */ - sqlite3_stmt *stmt; - sqlite3_prepare_v3(db, "SELECT COUNT(*) FROM cards", -1, 0, &stmt, NULL); - sqlite3_step(stmt); - int N = sqlite3_column_int(stmt, 0); - sqlite3_finalize(stmt); - - /* Get card weights */ - sqlite3_prepare_v3(db, "SELECT weight FROM cards", -1, 0, &stmt, NULL); - seg = (int*)malloc(4 * N * sizeof(int)); - build(stmt, 0, N - 1, 1); - sqlite3_finalize(stmt); - - if (verbose) { - for (int i = 0; i < 4 * N; i++) { - printf("%d ", seg[i]); - } - printf("\n"); - } - - /* Disable input buffering */ - system("stty -F /dev/tty cbreak min 1"); - system("stty -F /dev/tty -echo"); - - while (true) { - int x = (long long)rand() * rand() % seg[1]; - int res[2]; - query(res, x, 0, N-1, 1); - int w = res[0], i = res[1]; - - if (verbose) { - printf("%d %d %d %d\n", seg[1], x, w, i); - } - - /* Get card contents from database */ - sqlite3_prepare_v3(db, "SELECT key, val FROM cards WHERE idx=?", -1, 0, &stmt, NULL); - sqlite3_bind_int(stmt, 1, i); - sqlite3_step(stmt); - char *key, *val; - key = strdup(sqlite3_column_text(stmt, 0)); - val = strdup(sqlite3_column_text(stmt, 1)); - sqlite3_finalize(stmt); - - printf("> %s\n", key); - - /* Wait for confirmation */ - char b = getchar(); - printf("%s\n", val); - - /* Read user input */ - b = getchar(); - if (b == 'y') { - w >>= 1; - } - else if (b == 'n') { - w <<= 3; - } - else { - break; - } - - /* Update segment tree and database */ - update(i, w, 0, N - 1, 1); - sqlite3_prepare_v3(db, "UPDATE cards SET weight=? WHERE idx=?", -1, 0, &stmt, NULL); - sqlite3_bind_int(stmt, 1, w); - sqlite3_bind_int(stmt, 2, i); - sqlite3_step(stmt); - sqlite3_finalize(stmt); - } - - /* Cleanup */ - system("stty -F /dev/tty echo"); - sqlite3_close(db); -} diff --git a/sd.c b/sd.c new file mode 100644 index 0000000..21caa57 --- /dev/null +++ b/sd.c @@ -0,0 +1,111 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include "segmenttree.h" + +int main(int argc, char* argv[]) { + char *file = "cards"; + bool verbose = false; + + /* Proccess args */ + static struct option long_options[] = { + {"file", required_argument, NULL, 'f'}, + {"verbose", no_argument, NULL, 'v'} + }; + while (1) { + int option_index = 0; + int c = getopt_long(argc, argv, "f:v", long_options, &option_index); + if (c == -1) break; + switch (c) { + case 'f': file = strdup(optarg); break; + case 'v': verbose = true; break; + default: abort(); + } + } + + /* Seed the RNG */ + srand(time(0)); + + /* Connect to db */ + sqlite3 *db; + sqlite3_open(file, &db); + + /* Get number of cards */ + sqlite3_stmt *stmt; + sqlite3_prepare_v3(db, "SELECT COUNT(*) FROM cards", -1, 0, &stmt, NULL); + sqlite3_step(stmt); + int N = sqlite3_column_int(stmt, 0); + sqlite3_finalize(stmt); + + /* Get card weights */ + sqlite3_prepare_v3(db, "SELECT weight FROM cards", -1, 0, &stmt, NULL); + seg = (int*)malloc(4 * N * sizeof(int)); + build(stmt, 0, N - 1, 1); + sqlite3_finalize(stmt); + + if (verbose) { + for (int i = 0; i < 4 * N; i++) { + printf("%d ", seg[i]); + } + printf("\n"); + } + + /* Disable input buffering */ + system("stty -F /dev/tty cbreak min 1"); + system("stty -F /dev/tty -echo"); + + while (true) { + int x = (long long)rand() * rand() % seg[1]; + int res[2]; + query(res, x, 0, N-1, 1); + int w = res[0], i = res[1]; + + if (verbose) { + printf("%d %d %d %d\n", seg[1], x, w, i); + } + + /* Get card contents from database */ + sqlite3_prepare_v3(db, "SELECT key, val FROM cards WHERE idx=?", -1, 0, &stmt, NULL); + sqlite3_bind_int(stmt, 1, i); + sqlite3_step(stmt); + char *key, *val; + key = strdup(sqlite3_column_text(stmt, 0)); + val = strdup(sqlite3_column_text(stmt, 1)); + sqlite3_finalize(stmt); + + printf("> %s\n", key); + + /* Wait for confirmation */ + char b = getchar(); + printf("%s\n", val); + + /* Read user input */ + b = getchar(); + if (b == 'y') { + w >>= 1; + } + else if (b == 'n') { + w <<= 3; + } + else { + break; + } + + /* Update segment tree and database */ + update(i, w, 0, N - 1, 1); + sqlite3_prepare_v3(db, "UPDATE cards SET weight=? WHERE idx=?", -1, 0, &stmt, NULL); + sqlite3_bind_int(stmt, 1, w); + sqlite3_bind_int(stmt, 2, i); + sqlite3_step(stmt); + sqlite3_finalize(stmt); + } + + /* Cleanup */ + system("stty -F /dev/tty echo"); + sqlite3_close(db); +} -- cgit v1.2.3-70-g09d2