2
\$\begingroup\$

Let's say I have this pattern and a large array:

String [] pattern = new String[]{"i","am","a", "pattern"};
String [] large_array = new String[]{"not","i","am","a", "pattern","pattern","i","am","a", "pattern", "whatever", "x", "y", i","am","a", "pattern",................, i","am","a", "pattern" ....}; 

As you can see the pattern appears multiple times in the array. The first time at index 1, the second time at index 6, etc... I want to find out at which positions the pattern begins and return it in a collection (eg list).

In this case the position array is 1,6,13, etc...

Here is my current method:

private ArrayList<Integer> getStartPositionOfPattern(String[] headerArray, String[] pattern) {

    ArrayList<Integer> allPositions = new ArrayList<>();
    int idxP = 0, idxH = 0;
    int startPos = 0;
    while (idxH < headerArray.length) {
        if (pattern.length == 1) {
            if (pattern[0].equals(headerArray[idxH])) {
                allPositions.add(idxH);
            }
        } else {
            if (headerArray[idxH].equals(pattern[idxP])) {
                idxP++;
                if (idxP == pattern.length) { //you reached end of pattern
                    idxP = 0; //start Pattern from begining
                    allPositions.add(startPos); //you can save startPosition because pattern is finished
                }
            } else {
                idxP = 0;
                startPos = idxH + 1;
                if (pattern[idxP].equals(headerArray[idxH])) { //if current arrray.idxH is not pattern.idxP but array.idxH is begining of pattern
                    startPos = idxH;
                    idxP++;
                }
            }
        }

        idxH++;

    }
    return allPositions;
}

Is there a way to make my function more readable and faster? I believe it works correctly, but because the function is complex, I worry I might have an undetected bug.

NOTE: headerArray is the large array.

\$\endgroup\$
4
  • 3
    \$\begingroup\$ Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review. \$\endgroup\$ Commented Aug 21, 2018 at 20:46
  • \$\begingroup\$ A question like this is off topic for the code review site (which deals with reviewing existing code). If you are stuck you may want to search for string matching algorithms. KMP is probably what you want. \$\endgroup\$
    – spyr03
    Commented Aug 21, 2018 at 21:50
  • \$\begingroup\$ @spyr03 hope it helps now. \$\endgroup\$
    – plshm
    Commented Aug 21, 2018 at 23:16
  • \$\begingroup\$ @FreezePhoenix hope it helps now. \$\endgroup\$
    – plshm
    Commented Aug 21, 2018 at 23:16

2 Answers 2

0
\$\begingroup\$
  • Prefer returning List to ArrayList. Clients probably don’t need to know the type of list you’re dealing with. Likewise, you can declare your ArrayList as a List, since you don’t use any methods specific to ArrayList. This makes it easier to change your implementation later.

  • patternStartIndexes would be a better name than allPositions

  • Method variables should be declared on their own lines, and the names should be a lot more descriptive.
  • Your while loop might be more clear as a for loop with headerIndex as the loop variable.
  • The short-circuit you’re doing for patterns of length one is just noise. It’s a special case that should be correctly handled by the } else { block correctly.
  • Your implementation does not do what I would expect for special cases. I’m going to work under the assumption that your implementation is correct. If the pattern is { “a”, “a” } and the header array is { “a”, “a”, “a” }, is the desired output { 0 } or { 0, 1 }? If the latter, you’re going to need a second loop or a somewhat different approach.
  • I’m not convinced your comments add much. Non-javadoc comments are typically used to document why, not what. I think your code is pretty straightforward in terms of what it’s doing. You may disagree. :)
  • For readability, it’s nice to keep lines relatively short - maybe 120 characters, give or take. People are neither trained for or good at reading very long lines of text.
  • You don’t need to track startPosition, which lets us get rid of most of the else block. You can do math: startPosition = headerIndex - patternLength + 1.

If you make all the proposed modifications, your code might look something like:

private List<Integer> getPatternStartIndexes(final String[] headerArray, final String[] pattern) {

    final List<Integer> patternStartIndexes = new ArrayList<>();
    int patternIndex = 0;

    for (int headerIndex = 0; headerIndex < headerArray.length; headerIndex++) {
        if (headerArray[headerIndex].equals(pattern[patternIndex])) {
            patternIndex++;
            if (patternIndex == pattern.length) {
                patternIndex = 0;
                patternStartIndexes.add(headerIndex - pattern.length + 1);
            }
        } else {
            patternIndex = 0;
        }
    }
    return patternStartIndexes;
}
\$\endgroup\$
5
  • \$\begingroup\$ thanks fot the answert. But the method above does not seem to work if I have for example this: List<Integer> result = getPatternStartIndexes(new String[]{"V","A","V","A","V","A","N"},new String[]{"V","A","V","A","N"}); System.out.println(""+result.size()); //empty array \$\endgroup\$
    – plshm
    Commented Aug 22, 2018 at 18:40
  • \$\begingroup\$ @plshm Your code also returns an empty list. Did you read my 6th bullet point? "Your implementation does not do [..]" \$\endgroup\$
    – Eric Stein
    Commented Aug 22, 2018 at 19:26
  • \$\begingroup\$ yes my method returns an empty array if the pattern hasn't been found. But in this case there is a pattern which starts at index 2. Conserning bullet point six, the pattern should only return {0} \$\endgroup\$
    – plshm
    Commented Aug 22, 2018 at 19:48
  • \$\begingroup\$ @plshm Your code and my code return the same output for the same input. The reason is that if you find the beginning of a match, you start walking the input, and then when it stops being a match, you are effectively throwing out all the prior strings in the header array that were part of the potential match. \$\endgroup\$
    – Eric Stein
    Commented Aug 22, 2018 at 20:52
  • \$\begingroup\$ yeah it makes sence. I just tested it with wrong input before that is the reason I thought it works.... But is there actually a FAST way to prevent it. \$\endgroup\$
    – plshm
    Commented Aug 22, 2018 at 21:35
0
\$\begingroup\$

Naming

  1. NOTE: headerArray is the large array.

If you need to specify this to us, then your variable name isn't good. We should be able to understand your code with only your code because you wouldn't be beside us when we read it.

  1. Don't worry about using full names for your variables. After all, is there a real difference between idxP and indexPosition apart from the fact that it's very clear I'll understand the latter one?

Commenting

Every time you want to write a comment, ask yourself if it is necessary. When you think it is, think again! :p Comments suck (I'm not really talking about XML comments on methods and classes and etc). When you write a comment in a method, it's because there's something weird enough that you'd feel the need to explain why you did something much more than what you did. In your cases, I don't think the comments are necessary.

Readability

In my opinion, there are two great and easy ways to make code more readable.

  1. Extracting methods : Taking small chunks of your code that fills a single purpose and make a method out of it.

  2. Reduce nesting : Remove as much forking as possible (if, while, for, etc.)

When dealing with algorithms, it's often hard to extract methods as many things are dependent.

However, you have lots of forking, so we can work with that.

if (pattern.length == 1) {
    if (pattern[0].equals(headerArray[idxH])) {
        allPositions.add(idxH);
    }
}

Everytime (exceptions might apply lol) you have two if stuck one to another, they can be merged using the AND (&&) operator.

if (pattern.length == 1 && pattern[0].equals(headerArray[idxH])) {
    allPositions.add(idxH);
}    

Bam, nesting reduced.

You should try to find other ways to reduce nesting, but again, coding complex algorithms often imply spaghetti-ish code. And in this case, you might want to write a meaningful comment as to why your code is this way.

What's next?

If you really want to reach great performance for a "large" array, you might want to consider looking at String searching algorithms. It's not an exact fit to your problem, but there's something to be done.

Small nitpick : Large has a vague definition. If you want to make your code as correct as possible regarding your input, it can be useful to know an approximation of how much data your working with. For you, maybe an array with 100 elements is large, but for some data scientist at IBM, maybe it's 15000000.

\$\endgroup\$

Your Answer

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

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