CHC5223 Exercise on efficiency and Big O#

In the C programming language, and some others, (variable-length) a character string is held in the lowest-indexed elements of a (fixed-capacity) array, with a terminator immediately following the string. There must be (at least one) terminator; what follows the terminator in the array is not part of the string and is not of interest.

In C the terminator is the null character 0x0, but this invisible, so in the following exercise we use ’@’.

In this exercise you will consider various possible implementation of the operation trim, which works on a Java simulation of the C-type character string.

The static method makeArray takes a Java string passed as a parameter and updates a character array passed as parameter.

The method displayAll shows all the characters in the array with the C-type representation of the string.

The method displayAsString displays the string held in the array (and puts it inside quotes).

There are four implementations of the method trim (trim0, trim1, trim2, trim3). They each take a character array holding a (well formed) “string”, as described above, and they each purport to remove the occurrences of a character del (del ≠ terminator) from it, in situ.

Class-room tasks#

Study each of the implementations. The source text is at the end of this document.
Determine which of them is/are correct. If you need to, you can do this by “desk-checking” small examples. State in what way any are incorrect.
Try to determine by reasoning what the big-O complexity of each method is.
Explain your reasoning for each choice.
trim3 is very similar to trim2. Can you see where they differ? Does their big-O complexity differ?
Which implementation is best?

Practical tasks#

You should write a very simple program to use makeArray to convert a Java string to a C-type string; then try each version of trim on a sample string and use displayAll and displayAsString to show the outcome.
Example:

1
public static void main(String[] args) {
2
    char[] s= new char[15]; // make sure this is big enough
3
  String test = "/this//is//it/";
4
  makeArray(test, s);
5
  displayAll(s);
6
  System.out.println("trim0");
7
  trim0 (s, '/'); displayAll(s);
8
  displayAsString(s); System.out.println();
9
}

“Instrument” each version of trim to count and display its number of comparisons and its number of copy operations.
Example:

1
public static void trim0Instrumented(char[] s, char del) {
2
  // pre: exists i: 0 <= i < s.length: s[i] == terminator &&
3
  // del != terminator
4
  assert del != terminator;
5
  int comps = 0, copies = 0;
6
  int i = 0, j = 0;
7
  comps++; // head of while
8
  while(s[i] != terminator) {
9
    comps++; // ahead of if
10
        if (s[i] == del) {
11
      j = i;
12
      comps++; // head of while
13
      while(s[j + 1] != terminator) {
14
          s[j] = s[j + 1]; j++;
15
          copies++;
16
          comps++; // next of while
17
      }
18
      s[j] = terminator;
19
      copies++;
20
    }
21
    i++;
22
    comps++; // next of while
23
  }
24
    System.out.println("trim 0: comparisons = " + comps + " copies = " + copies);
25
} // trim0Instrumented

Repeat your tests using the instrumented versions.
Do the results accord with the results of you reasoned in the class-room part of this exercise?

The Java sources#

1
public class Trim {
2
    static final char terminator = '@';
3

4
    public static void makeArray(String str, char[] s) {
5
        int i;
6
        for(i = 0; i != str.length(); i++) s[i] = str.charAt(i);
7
        s[i] = terminator;
8
    }
9

10
    public static void displayAll(char [] s) {
11
        for (int i = 0; i != s.length; i++) System.out.print(s[i]);
12
    }
13

14
    public static void displayAsString(char [] s) {
15
        int i = 0;
16
        System.out.print("\"");
17
        while(s[i] != terminator){
18
            System.out.print(s[i]); i++;
19
        }
20
        System.out.print("\"");
21
    }
22
    public static void trim0(char[] s, char del) {
23
        // pre: exists i: 0 <= i < s.length: s[i] == terminator &&
24
        // del != terminator
25
        assert del != terminator;
26
        int i = 0, j;
27
        while(s[i] != terminator) {
28
            if (s[i] == del) {
29
                j = i;
30
                while(s[j + 1] != terminator) {
31
                    s[j] = s[j + 1]; j++;
32
                }
33
                s[j] = terminator;
34
            }
35
            i++;
36
        }
37
    } // trim0
38

39
    public static void trim1(char[] s, char del) {
40
        // pre: exists i: 0 <= i < s.length: s[i] == terminator &&
41
        // del != terminator
42
        assert del != terminator;
43
        int i = 0, j;
44
        while(s[i] != terminator) {
45
            if (s[i] == del) {
46
                j = i;
47
                while(s[j + 1] != terminator) {
48
                    s[j] = s[j + 1]; j++;
49
                }
50
                s[j] = terminator;
51
            }
52
            else i++;
53
            }
54
    } // trim1
55

56
    public static void trim2(char[] s, char del) {
57
        // pre: exists i: 0 <= i < s.length: s[i] == terminator &&
58
        // del != terminator
59
        assert del != terminator;
60
        int i = 0, j = 0;
61
        while(s[i] != terminator) {
62
            if (s[i] != del) {
63
                s[j] = s[i]; j++;
64
            }
65
            i++;
66
        }
67
        s[j] = terminator;
68
    } // trim2
69

70
    public static void trim3(char[] s, char del) {
71
        // pre: exists i: 0 <= i < s.length: s[i] == terminator &&
72
        // del != terminator
73
        assert del != terminator;
74
        int i, j;
75
        i = 0; j = 0;
76
        while(s[i] != terminator) {
77
            while (s[i] == del)
78
                i++;
79
            // s[i] != del)
80
            if (s[i] != terminator){
81
                s[j] = s[i];  j++; i++;
82
            }
83
        }
84
        s[j] = terminator;
85
    } // trim3
86
}

Tip

Time complexity:

trim0: $O(n^2)$
trim1: $O(n^2)$
trim2: $O(n)$
trim3: $O(n)$

Caution

嵌套 while 循环不一定导致时间复杂度指数级增加

音乐

音乐

CHC5223 Exercise on efficiency and Big O#

Class-room tasks#

Practical tasks#

The Java sources#

支持与分享

评论区

音乐

目录

音乐

音乐

Efficiency and Big O

CHC5223 Exercise on efficiency and Big O#

Class-room tasks#

Practical tasks#

The Java sources#

支持与分享

评论区

音乐

目录