Skip to content

Instantly share code, notes, and snippets.

@MilesCranmer
Created June 26, 2022 01:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save MilesCranmer/d262f468d570df4b90c8769ebdcce213 to your computer and use it in GitHub Desktop.
Save MilesCranmer/d262f468d570df4b90c8769ebdcce213 to your computer and use it in GitHub Desktop.
Get unique elements of an array using a lookup table
// 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