Removing duplicate words from an unsorted list

Question

I was using brute force to remove duplicate words since the lists were really small. But I want a solution that won't become too slow if the input grows.

This function creates a binary tree and inserts all words appearing on the list, then collects the unique words without sorting. Duplicate words are handled during insertion. For the tree, I'm using about the same code from Unbalanced binary search tree.

#include "bst.h"
#include <strings.h>
#include <stdlib.h>

#define LIST_TERMINATOR 1

static size_t i = 0;
static char **final_list;

static void insert(void *word)
{
    final_list[i++] = word;
}

char **unique_words(const char **words)
{
    //Binary tree containing the words
    BST unique;
    bst_init(&unique, (int(*)(const void *, const void *))strcasecmp);

    //Every word will be inserted at most 1 time
    while(*words != NULL){
        if(bst_insert(&unique, (void *)*words) == BST_NO_MEMORY){
            bst_free(&unique);
            return NULL;
        }

        ++words;
    }

    //Array to return
    final_list = malloc(sizeof(char *) * (unique.node_count + LIST_TERMINATOR));
    if(final_list == NULL){
        bst_free(&unique);
        return NULL;
    }

    //Collect words without sorting, so if the list is merged with another 
    //and passed again, the tree won't become a linked list
    if(bst_iterate_top_down(&unique, insert) == BST_NO_MEMORY){
        free(final_list);
        bst_free(&unique);
        return NULL;
    }
    final_list[i] = NULL;

    bst_free(&unique);

    //Clear state
    i = 0;

    return final_list;
}

Would sorting the input then removing duplicates be faster?

Answer 1

This question boils down to the number and sequence of operations. If you are building one large list but removing lots of duplicates, use a hash table or sort and uniquify the list.

Sorting and making the list unique is O(n log n) at best. Removing a duplicate is O(n) at worst so removing m duplicates is O(m * n). While in general O(k * n) = O(n), once m exceeds log n the one-time cost of sorting the set pays for itself. And additional lookups remain O(1).

You must evaluate the costs with realistic values for m and n to decide which method is better. Of course, their values will vary over time along with the relative costs of CPU versus RAM versus disk. But for most "probable" values of m and n over time, relying on standard library collection classes--with a sprinkle of tuned variations from Guava and the like--is the hands-down winner.