Teil-Array

[flashdog]

Hallo,
ich habe ein Array und ein Teil-Array. Das größere Array beinhaltet das Teil-Array. Das folgende Programm findet die Index Position an welcher stelle das Teil-Array in dem größeren Array beginnt.

public class FindeIndex {
	public static int findeIndexPos(int arr1[] , int arr2[]){
		int pos = 0;
		
		System.out.print("Array: ");
		for(int i : arr1){
			System.out.print(i + " ");
		}
		
		System.out.print("\nTeilarray: ");
		for(int i : arr2){
			System.out.print(i + " ");
		}
		System.out.println();
		
		for (int i = 0; i < arr1.length; i++){
			if (arr1[i] == arr2[0]){
				System.out.print("Ergebnis: " + i);
				break;
			}				
		}
		return pos;
	}

	public static void main(String[] args) {
		int tArray1[] = {3, 4, 6, 7, 8};
		int tArray2[] = {6, 7};

		findeIndexPos(tArray1, tArray2);
	}
}

Ausgabe:

Array: 3 4 6 7 8 
Teilarray: 6 7 
Ergebnis: 2

Das obere Programm hat aber zwei Probleme. Der erste ist, dass ich davon ausgehe, dass es wirklich ein Teil-Array ist da ich nicht weiss wie man das testen kann.
Das zweite Problem ist, dass ich nur die erste Index Postion in dem größeren Array für den beginn des Teil-Arrays annehme, aber dies ist keine Garantie für den beginn des Teil-Arrary im Arrary.

Wie kann man die zwei Probleme beheben und mit Sicherheit festellen ab welcher stelle der Teil-Array im größeren Array beginnt?

Viele Grüße

 

[faetzminator]

ich würde folgendes vorschlagen, die Laufzeit beträgt Worstcase aber leider O(n*m):

public static int findeIndexPos(int arr1[], int arr2[]) {
    boolean isCorrect;
    for (int i = 0; i < arr1.length - arr2.length; i++) {
        isCorrect = true;
        for (int j = 0; j < arr2.length; j++) {
            if (arr1[i + j] != arr2[j]) {
                isCorrect = false;
                break;
            }
        }
        if (isCorrect) {
            return i;
        }
    }
    return -1;
}

 

[flashdog]

Vielen Dank es funktioniert.

Wie könnte man das Programm mit JUnit testen?

 

[diggaa1984]

definier dir 2 arrays und schau ob die richtigen werte herauskommen!?

 

[flashdog]

Danke, aber wie würde der JUnit code dafür aussehen?

 

[0x7F800000]

Danke, aber wie würde der JUnit code dafür aussehen?

Wie ein stinknormaler JUnit Testcase eben... Wie sieht es denn bisher aus?

 

[flashdog]

Leider funktioniert JUnit bei mir nicht. Ich habe extra falsche erwartugswerte angeben, aber trotzdem läuft der Test fehlerfrei durch:

import junit.framework.*;

public class TestFindeIndex extends TestCase {
	FindeIndex f;

	public TestFindeIndex(String name) {
		super(name);
	}

	public void setUp(){
		f=new FindeIndex();
	}

	public static Test suite() {
		return new TestSuite(TestFindeIndex.class);
	}

	public void test1() {
		int tArray1[] = {3, 4, 6, 7, 8};
		int tArray2[] = {6, 7};
		
		assert(f.findeIndexPos(tArray1, tArray2) == 1); // richtig waere 2
	}

	public void test2() {
		int tArray1[] = {3, 6, 4, 6, 7, 8};
		int tArray2[] = {6, 7};
		
		assert(f.findeIndexPos(tArray1, tArray2) == 1); // richtig waere 3
	}
	
	public static void main(String args[]) {
		junit.textui.TestRunner.run(suite());
	}
}

Was habe ich falsch gemacht?

 

[faetzminator]

anstatt [c]assert(x == y)[/c] musst du [c]assertEquals(x, y)[/c] verwenden

 

[flashdog]

Danke es hat funktioniert.

 

[bygones]

versuch dir aber anzugewoehnen mit JUnit4 zu arbeiten...

weiterhin kannst du dir mal Hamcrest anschauen - das macht das matchen bzw assert um einiges verstaendlicher

 

[flashdog]

Ich dachte ich habe JUnit 4 verwendet. Wie würde es in JUnit 4 aussehen?

 

[Landei]

Ich schlage eine andere Implementierung vor:

  public static int indexOf(int[] ps, int[] qs) {
    if (ps.length < qs.length) {
      return -1;
    }
    int qsum = 0;
    for(int q : qs) {
      qsum += q; 
    }
    int psum = 0;
    for(int i = 0; i < qs.length; i++) {
      psum += ps[i];
    }
    for(int i = 0; i < ps.length - qs.length; i++) {
      if (i > 0) {
        psum += ps[i+qs.length] - ps[i-1];
      }
      if(psum == qsum) {
        boolean found = true;
        for(int k = 0; k < qs.length; k++) {
          if (qs[k] != ps[k + i]) {
            found = false;
            break;
          }
        }
        if(found) {
          return i;
        }
      }
    }
    return -1;    
  }

Dabei werden die Stellen, die "genauer untersucht werden" anders bestimmt. Während im Original geschaut wurde, ob die beiden Anfangswerte gleich sind, schaue ich nach, ob die Summe der Teil-Sequenz mit der Summe der gesuchten Sequenz übereinstimmt. Ich denke, dass man damit in der Praxis besser fährt, weil mehr Informationen in die Berechnung eingehen (es lassen sich aber bestimmt Beispiele mit gleichem Worst-Case-Verhalten konstruieren). Die Berechnung erfolgt "gleitend", also um das "Sequenz-Fenster" um eins zu verschieben, ziehe ich den alten Anfangswert ab und addiere den neuen Endwert dazu.

 

[bygones]

Ich dachte ich habe JUnit 4 verwendet. Wie würde es in JUnit 4 aussehen?

Junit4 arbeitet mit Annotations

public class TestFindeIndex {
    private FindeIndex f;
    
    @Before 
    public void setUp(){
        // wird vor jedem test aufgerufen
        f=new FindeIndex();
    }
 
    @Test
    public void test1() {
       // test
    }
 
    @Test
    public void test2() {
        // test
    }

}

 

[flashdog]

Netbeans hat mir Junit 4 vorbereit und ich habe nur
int[] arr1 = {3, 4, 6, 7, 8};
int[] arr2 = {6, 7};
int expResult = 2;
deklaliert, aber leider läuft der Test nicht Fehlerfrei ab.

import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
import static org.junit.Assert.*;


public class FindeIndexTest {

  public FindeIndexTest() {
  }

  @BeforeClass
  public static void setUpClass() throws Exception {
  }

  @AfterClass
  public static void tearDownClass() throws Exception {
  }

  @Before
  public void setUp() {
  }

  @After
  public void tearDown() {
  }

  /**
   * Test of findeIndexPos method, of class FindeIndex.
   */
  @Test
  public void testfindeIndexPos() {
    System.out.println("findeIndexPos");
    int[] arr1 = {3, 4, 6, 7, 8};
    int[] arr2 = {6, 7};
    int expResult = 2;
    int result = FindeIndex.findeIndexPos(arr1, arr2);
    assertEquals(expResult, result);
    // TODO review the generated test code and remove the default call to fail.
    fail("The test case is a prototype.");
  }
  /**
   * Test of main method, of class FindIndex.
   */
//  @Test
//  public void testMain() {
//    System.out.println("main");
//    String[] args = null;
//    FindeIndex.main(args);
//    // TODO review the generated test code and remove the default call to fail.
//    fail("The test case is a prototype.");
//  }
}

Was habe ich vergessen?

 

[Landei]

Schon mal ohne das fail("The test case is a prototype.") probiert?

 

[flashdog]

Danke, es hat funktioniert.