2
\$\begingroup\$

Challenge:

Swap positions in a list

Specifications:

Your program should accept as its first argument a path to a filename.
The file contains several test cases, one on each line.
Each test case is a list of numbers, supplemented with positions to be swapped.
List and positions are separated by a colon.
Positions start with 0.
There may be more than one position swaps, separated by a comma.
Positions swaps are processed left to right.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class SwapElements {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));

        while (input.hasNextLine()) {
            String[] temp = input.nextLine().split(":");
            printSwapped(swapList(temp[0], temp[1]));
        }
    }

    public static void printSwapped(List<String> list) {
        StringBuilder result = new StringBuilder();

        for (String s : list) {
            result.append(' ').append(s);
        }

        System.out.println(result.substring(1));
    }

    public static List<String> swapList(String input, String swapKey) {
        List<String> result = modifyToList(input);

        for (String s : swapKey.split(",")) {
            String[] keys = s.split("-");
            int index1 = Integer.parseInt(keys[0].substring(1));
            int index2 = Integer.parseInt(keys[1]);

            String target1 = result.get(index2);
            String target2 = result.get(index1);

            result.set(index1, target1);
            result.set(index2, target2);
        }

        return result;
    }

    public static List<String> modifyToList(String list) {
        List<String> result = new ArrayList<>(list.length());

        for (String s : list.split("\\s+")) {
            result.add(s);
        }

        return result;
    }   
}

Sample Input:

1 2 3 4 5 6 7 8 9 : 0-8
1 2 3 4 5 6 7 8 9 10 : 0-1, 1-3

Sample Output:

9 2 3 4 5 6 7 8 1
2 4 3 1 5 6 7 8 9 10

It's actually been a while since I did one of these and I get the feeling it shows. The solution itself, of course, works, but I get the sense that it's memory intensive and/or slow. I'd mostly like to focus on optimizing speed, but any and all general feedback is welcome.

What do you think?

\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

Switching from a List<Integer> to an int[] speeds things up quite a bit, for the input examples you've provided. Note: I've slightly simplified your code to work off a fixed array of strings, merely because it made my testing easier.

public class SwapElements {

  private static final String[] lines = { "1 2 3 4 5 6 7 8 9 : 0-8",
      "1 2 3 4 5 6 7 8 9 10 : 0-1, 1-3" };

  public static void main(String[] args) throws Exception {
    for (String line : lines) {
      String[] temp = line.split(":");
      int[] numbers = toPrimitiveArray(temp[0]);
      printSwapped(swapList(numbers, temp[1]));
    }
  }

  private static int[] toPrimitiveArray(String input) {
    String[] numbers = input.split(" ");

    int[] result = new int[numbers.length];
    for (int i = 0; i < numbers.length; i++) {
      result[i] = Integer.parseInt(numbers[i]);
    }
    return result;
  }

  private static void printSwapped(int[] list) {
    StringBuilder result = new StringBuilder();

    for (int i : list) {
      result.append(' ').append(i);
    }

    System.out.println(result.substring(1));
  }

  private static int[] swapList(int[] input, String swapKey) {
    for (String s : swapKey.split(",")) {
      String[] keys = s.split("-");
      int index1 = Integer.parseInt(keys[0].substring(1));
      int index2 = Integer.parseInt(keys[1]);

      int target1 = input[index2];
      int target2 = input[index1];

      input[index1] = target1;
      input[index2] = target2;
    }

    return input;
  }
}

Some basic benchmarking showed me that this improved performance from 4,125ns to 2,536ns (almost 40% reduction), for processing both input strings.

Other comments:

  • I've changed most of your public methods to private, since they don't appear to be used outside of the class.
  • Your original code doesn't correctly close the Scanner you use. These days, you can avoid that entire problem using NIO classes:

    List<String> fileLines = Files.readAllLines(Paths.get(args[0]));
    
  • You may wish to refactor your code to introduce a int[] swapElements(String input) method, so you can unit test more easily.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.