How to delete specific sym links in $HOME given a list of their coordinating files in O(n lg n)?

Question

I've made a manager for my dot files that creates sym links between each of the dot files in my dot_files/ dir and my $HOME.

I'm trying to write a script that deletes all of these specific sym links and no others.

Here's my O(n^2) solution that does the job fine.

delete_sym_links () {
    # Include dot (.) files while looping
    shopt -s dotglob

    for DOT_FILE in ~/dot_files/*;
    do
        if [ ! -d "$DOT_FILE" ];
        then
            for FILE in ~/*;
            do
                if [ -h "$FILE" ] && [ $(basename $DOT_FILE) = $(basename $FILE) ];
                then
                    rm "$FILE"
                    echo deleted "$FILE"
                fi
            done
        fi
    done
}

I'm trying to get the runtime down to O(n lg n). The bash is really tripping me up though.

Something like...

delete_sym_links () {
    SYM_LINKS=($(find $HOME -maxdepth 1 -type l -ls | sort -n))
    NUM_SYM_LINKS=$(find $HOME -maxdepth 1 -type l -ls | wc -l)
    DOT_FILES=$(find $HOME/dot_files/ -maxdepth 1 -name ".*" -type f | sort -n)
    NUM_DOT_FILES=$(find $HOME/dot_files/ -maxdepth 1 -name ".*" -type f | wc -l)

    i=0
    j=0

    while (("$i" < "$NUM_SYM_LINKS")) && (("$j" < "$NUM_DOT_FILES"));
    do
        if [ $(basename ${SYM_LINKS[$i]}) = $(basename ${DOT_FILES[$j]}) ];
        then
            echo removing sym link ${SYM_LINKS[$i]}
            rm ${SYM_LINKS[$i]}
            ((j++))
        else
            ((i++))
        fi
    done

    echo "All dot_files sym links removed"
}

Why are you looping over every file in your home directory when you know what the name should be? Essentially you could do what you were already doing in your n^2 version, but just set $FILE to `~/$(basename $DOT_FILE)`. — Tyler Marshall, Apr 03 '19 at 16:11
Even ignoring the big-O complexity, your constant factors are going to kill you on some of this (for any significantly-sized `n`) as the code is currently written -- `$(...)` is itself a slow operation, and running external commands (like basename) pays a large penalty as well. — Charles Duffy, Apr 03 '19 at 19:25
Re: `arr=( $(find ...) )`, see [BashPitfalls #50](http://mywiki.wooledge.org/BashPitfalls#hosts.3D.28_.24.28aws_....29_.29) -- that's not just a practice with performance issues but major correctness problems (a filename with spaces will be split into multiple array elements; a filename that can be expanded as a glob *will* be, and the results subject to `globfail` or `nullglob` behaviors if enabled; etc); better practices are discussed in [UsingFind](http://mywiki.wooledge.org/UsingFind). — Charles Duffy, Apr 03 '19 at 19:27
...in particular, consider `readarray -t -d '' arr < <(find ... -print0)`. — Charles Duffy, Apr 03 '19 at 19:29

score 4 · Accepted Answer · answered Apr 03 '19 at 19:19

Try this Shellcheck-clean, O(n), code:

function delete_symlinks
{
    local df_path df_name home_df_path

    for df_path in ~/dot_files/.* ; do
        [[ -d $df_path ]] && continue
        df_name=${df_path##*/}
        home_df_path=~/$df_name
        if [[ -L $home_df_path ]] ; then
            rm -- "$home_df_path"
            printf 'deleted %s\n' "$home_df_path"
        fi
    done

    return 0
}

It uses a ksh-style function definition (a personal preference).
All variables are localized to avoid clashes with global variables.
Lowercase is used for all variable names. See Correct Bash and shell script variable capitalization.
It uses [[ instead of [ for tests. See Is double square brackets [[ ]] preferable over single square brackets [ ] in Bash?
${var##*/} is used instead of $(basename $var) for safety and speed. See Removing part of a string (BashFAQ/100 (How do I do string manipulation in bash?)).
printf is used instead of echo for safety. See the accepted, and excellent, answer to Why is printf better than echo?.
As in the code in the question, no attempt is made to check that the symlink being deleted actually links to the corresponding file under 'dotfiles'. I would fix this in a real program because it might remove a manually-created symlink.

Great, well-referenced answer; I find myself upvoting it despite the ksh function declaration syntax :P — Charles Duffy, Apr 03 '19 at 19:23

score 1 · Answer 2 · answered Apr 03 '19 at 19:19

bash has associative arrays. We can store a unique identifier for each dotfile and then check the home directory files for a match. I believe this is O(m+n) compared to your original O(m*n).

Here's an example using inode:

delete_sym_links () (
    declare -A inode
    shopt -s dotglob nullglob

    ls -diL ~/dot_files/* | (
        while read i name; do
            [ ! -f "$name" ] && continue
            inode2name[$i]="$name"
        done
        for name in ~/*; do
            [ ! -h "$name" ] && continue

            read i junk <<<$( ls -diL "$name" )
            if [ "$junk" != "$name" ]; then
                echo 1>&2 "ls parse error! ($name)"
            fi
            if [ -n "${inode2name[i]}" ]; then
                echo "found: $name -> ${inode2name[$i]}"
                echo "rm \"$name\""
            fi
        done
    )
)

As ~/dot_files/ is a subdirectory of ~/, I have assumed they are on the same filesystem so that inode can be used as the unique id.
Parsing ls (in the while loop) is frowned upon but is a portable way to extract the inode as long as we don't have strange filenames (eg. with embedded newlines). We only need POSIX options.
We call ls rather a lot in the for loop so it could have a big effect on the constant factor of the complexity, but it's only on possible matches so perhaps it's not so bad.
Using fn()() instead of more common fn(){} localises the shopt

If we don't like parsing ls but we have realpath, we can do:

delete_sym_links () (
    declare -A real
    shopt -s dotglob nullglob

    for name in ~/dot_files/*; do
        [ ! -f "name" ] && continue
        real="$(realpath "$name")"
        real2name["$real"]="$name"
    done

    for name in ~/*; do
        [ ! -h "$name" ] && continue
        real="$(realpath "$name")"
        if [ -n "${real2name["$real"]}" ]; then
            echo 1>&2 "found: $name -> ${real2name["$real"]}"
            echo "rm \"$name\""
        fi
    done
)

How to delete specific sym links in $HOME given a list of their coordinating files in O(n lg n)?

2 Answers2