Created
June 26, 2022 01:58
-
-
Save MilesCranmer/d262f468d570df4b90c8769ebdcce213 to your computer and use it in GitHub Desktop.
Get unique elements of an array using a lookup table
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Count elements of an array by using a lookup table. | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <stdbool.h> | |
#include <time.h> | |
int main(int argc, char *argv[]) | |
{ | |
// Generate random array of integers, with | |
// size given by args. | |
int max_int = atoi(argv[1]); | |
int array_size = atoi(argv[2]); | |
bool do_counting = atoi(argv[3]); | |
// Create array of integers: | |
int *array = malloc(array_size * sizeof(int)); | |
for (int i = 0; i < array_size; i++) | |
{ | |
array[i] = rand() % max_int; | |
} | |
// Start timer: | |
clock_t start = clock(); | |
int *unique; | |
int *unique_counts; | |
if (do_counting) | |
{ | |
// Create array to count elements: | |
int *count = calloc(max_int, sizeof(int)); | |
// Count elements: | |
for (int i = 0; i < array_size; i++) | |
{ | |
count[array[i]]++; | |
} | |
// Count number nonzero: | |
int nonzero = 0; | |
for (int i = 0; i < max_int; i++) | |
{ | |
if (count[i] != 0) | |
{ | |
nonzero++; | |
} | |
} | |
// Create array containing unique elements of array, | |
// and another array with their count: | |
unique = malloc(nonzero * sizeof(int)); | |
unique_counts = calloc(nonzero, sizeof(int)); | |
int j = 0; | |
for (int i = 0; i < max_int; i++) | |
{ | |
if (count[i] != 0) | |
{ | |
unique[j] = i; | |
unique_counts[j] = count[i]; | |
j++; | |
} | |
} | |
} | |
else // don't do counting | |
{ | |
// Create array to mask elements | |
bool *count = calloc(max_int, sizeof(bool)); | |
// Mask existing elements: | |
for (int i = 0; i < array_size; i++) | |
{ | |
count[array[i]] = true; | |
} | |
// Count number nonzero: | |
int nonzero = 0; | |
for (int i = 0; i < max_int; i++) | |
{ | |
if (count[i] != 0) | |
{ | |
nonzero++; | |
} | |
} | |
// Create array containing unique elements of array, | |
// and another array with their count: | |
unique = malloc(nonzero * sizeof(int)); | |
unique_counts = malloc(nonzero * sizeof(int)); | |
// ^ We don't actually do anything with this. | |
int j = 0; | |
for (int i = 0; i < max_int; i++) | |
{ | |
if (count[i]) | |
{ | |
unique[j] = i; | |
j++; | |
} | |
} | |
} | |
// Stop timer: | |
clock_t end = clock(); | |
// Prevent C from cheating, but writing first 10 elements to file: | |
FILE *file = fopen("output.txt", "w"); | |
for (int i = 0; i < 10; i++) | |
{ | |
fprintf(file, "%d\n", unique[i]); | |
fprintf(file, "%d\n", unique_counts[i]); | |
} | |
// Print time: | |
printf("Time: %f\n", (double)(end - start) / CLOCKS_PER_SEC); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment