[重庆]将新建三条快速通道 打通向西“瓶颈”

Question

I have implemented an elementary positive integer class that supports addition, subtraction, and multiplication for an arbitrary number of digits using a singly linked list.

class Node
{
    Node ref_prev_node;
    int value;

    Node(int n)
    {
        this.ref_prev_node = null;
        this.value = n;
    }
}

class MyBigInt
{
    private Node ref_tail_node;
    private int size;

    private MyBigInt()
    {
        this.ref_tail_node = null;
        this.size = 0;
    }

    MyBigInt(String s)
    {
        if (s.length() == 0)
        {
            throw new IllegalStateException("Can't construct MyBigInt using an empty string!");
        }

        Node ref_old_node = null;

        for (int i = s.length() - 1; i >= 0; --i)
        {
            if (!(Character.isDigit(s.charAt(i))))
            {
                throw new IllegalStateException("Can't construct MyBigInt using non-digit characters!");
            }

            Node ref_new_node = new Node((int) (s.charAt(i) - '0'));

            if (i == s.length() - 1)
            {
                this.ref_tail_node = ref_new_node;
            }

            else
            {
                ref_old_node.ref_prev_node = ref_new_node;
            }

            ref_old_node = ref_new_node;

            ++(this.size);
        }

        this.trim_leading_zeroes();
    }

    MyBigInt add(MyBigInt n)
    {
        this.trim_leading_zeroes();
        n.trim_leading_zeroes();

        Node ref_curr_node_1 = this.ref_tail_node;
        Node ref_curr_node_2 = n.ref_tail_node;

        int carry = 0;
        MyBigInt ans = new MyBigInt();
        Node ref_old_node = null;

        while ((ref_curr_node_1 != null) || (ref_curr_node_2 != null) || (carry != 0))
        {
            int sum = (ref_curr_node_1 == null ? 0 : ref_curr_node_1.value) + (ref_curr_node_2 == null ? 0 : ref_curr_node_2.value) + carry;

            carry = sum / 10;

            Node ref_new_node = new Node(sum % 10);

            if (ans.ref_tail_node == null)
            {
                ans.ref_tail_node = ref_new_node;
            }

            else
            {
                ref_old_node.ref_prev_node = ref_new_node;
            }

            ref_old_node = ref_new_node;

            if (ref_curr_node_1 != null)
            {
                ref_curr_node_1 = ref_curr_node_1.ref_prev_node;
            }

            if (ref_curr_node_2 != null)
            {
                ref_curr_node_2 = ref_curr_node_2.ref_prev_node;
            }

            ++(ans.size);
        }

        return ans;
    }

    private void insert_trailing_zeroes(int number_of_zeroes)
    {
        if (number_of_zeroes > 0)
        {
            Node ref_new_tail_node = null;
            Node ref_old_node = null;

            for (int i = 0; i < number_of_zeroes; ++i)
            {
                Node ref_new_node = new Node(0);

                if (i == 0)
                {
                    ref_new_tail_node = ref_new_node;
                }

                else
                {
                    ref_old_node.ref_prev_node = ref_new_node;
                }

                ref_old_node = ref_new_node;
            }

            ref_old_node.ref_prev_node = this.ref_tail_node;
            this.ref_tail_node = ref_new_tail_node;
            this.size += number_of_zeroes;
        }
    }

    boolean is_greater_than_or_equal_to(MyBigInt n)
    {
        this.trim_leading_zeroes();
        n.trim_leading_zeroes();

        if (this.size > n.size)
        {
            return true;
        }

        else if (this.size < n.size)
        {
            return false;
        }

        else
        {
            int digit_1 = -1;
            int digit_2 = -1;

            Node ref_curr_node_1 = this.ref_tail_node;
            Node ref_curr_node_2 = n.ref_tail_node;

            while (ref_curr_node_1 != null)
            {
                if (ref_curr_node_1.value != ref_curr_node_2.value)
                {
                    digit_1 = ref_curr_node_1.value;
                    digit_2 = ref_curr_node_2.value;
                }

                ref_curr_node_1 = ref_curr_node_1.ref_prev_node;
                ref_curr_node_2 = ref_curr_node_2.ref_prev_node;
            }

            return digit_1 >= digit_2;
        }
    }

    MyBigInt multiply(MyBigInt n)
    {
        this.trim_leading_zeroes();
        n.trim_leading_zeroes();

        Node ref_curr_node_2 = n.ref_tail_node;

        MyBigInt ans = new MyBigInt("0");

        for (int i = 0; ref_curr_node_2 != null; ++i)
        {
            MyBigInt temp = this.multiply_single_digit(ref_curr_node_2.value);
            temp.insert_trailing_zeroes(i);
            ans = ans.add(temp);

            ref_curr_node_2 = ref_curr_node_2.ref_prev_node;
        }

        return ans;
    }

    private MyBigInt multiply_single_digit(int digit)
    {
        Node ref_curr_node = this.ref_tail_node;

        int carry = 0;
        MyBigInt ans = new MyBigInt();
        Node ref_old_node = null;

        while ((ref_curr_node != null) || (carry != 0))
        {
            int product = ((ref_curr_node == null ? 0 : ref_curr_node.value) * digit) + carry;

            carry = product / 10;

            Node ref_new_node = new Node(product % 10);

            if (ans.ref_tail_node == null)
            {
                ans.ref_tail_node = ref_new_node;
            }

            else
            {
                ref_old_node.ref_prev_node = ref_new_node;
            }

            ref_old_node = ref_new_node;

            if (ref_curr_node != null)
            {
                ref_curr_node = ref_curr_node.ref_prev_node;
            }

            ++(ans.size);
        }

        ans.trim_leading_zeroes();
        return ans;
    }

    MyBigInt subtract(MyBigInt n)
    {
        this.trim_leading_zeroes();
        n.trim_leading_zeroes();

        if (!(this.is_greater_than_or_equal_to(n)))
        {
            throw new IllegalStateException("Can't subtract larger MyBigInt from smaller MyBigInt!");
        }

        Node ref_curr_node_1 = this.ref_tail_node;
        Node ref_curr_node_2 = n.ref_tail_node;

        int carry = 0;
        MyBigInt ans = new MyBigInt();
        Node ref_old_node = null;

        while ((ref_curr_node_1 != null) || (ref_curr_node_2 != null))
        {
            int diff = ref_curr_node_1.value - (ref_curr_node_2 == null ? 0 : ref_curr_node_2.value) - carry;

            carry = (diff < 0) ? 1 : 0;
            diff = (diff < 0) ? (diff + 10) : diff;

            Node ref_new_node = new Node(diff);

            if (ans.ref_tail_node == null)
            {
                ans.ref_tail_node = ref_new_node;
            }

            else
            {
                ref_old_node.ref_prev_node = ref_new_node;
            }

            ref_old_node = ref_new_node;

            if (ref_curr_node_1 != null)
            {
                ref_curr_node_1 = ref_curr_node_1.ref_prev_node;
            }

            if (ref_curr_node_2 != null)
            {
                ref_curr_node_2 = ref_curr_node_2.ref_prev_node;
            }

            ++(ans.size);
        }

        ans.trim_leading_zeroes();
        return ans;
    }

    String to_string()
    {
        String s = new String();

        Node ref_curr_node = this.ref_tail_node;

        while (ref_curr_node != null)
        {
            s = ref_curr_node.value + s;
            ref_curr_node = ref_curr_node.ref_prev_node;
        }

        if (this.size != s.length())
        {
            throw new IllegalStateException("The 'size' data member of this MyBigInt does not represent its actual size!");
        }

        return s;
    }

    private void trim_leading_zeroes()
    {
        if (this.size > 0)
        {
            // If there is only node, then that node will be considered as the
            // leftmost node, even if it is zero. Else, we will look for the
            // leftmost non-zero node.
            Node ref_leftmost_node = this.ref_tail_node;
            int size_leftmost_node = 1;

            Node ref_curr_node = this.ref_tail_node.ref_prev_node;

            for (int i = 2; ref_curr_node != null; ++i)
            {
                if (ref_curr_node.value > 0)
                {
                    ref_leftmost_node = ref_curr_node;
                    size_leftmost_node = i;
                }

                ref_curr_node = ref_curr_node.ref_prev_node;
            }

            ref_leftmost_node.ref_prev_node = null;
            this.size = size_leftmost_node;
        }
    }
}

Answer 1

Use

First of all, I'll assume that this is an exercise, as java.math.BigInteger already provides most of the functionality that is specified. It is also backed by specialized native code in most Java VM's.

Using a linked list instead of an array of 32-bit integers or 64-bit longs is also far less performant. The only advantage could be to avoid memory copies as Java BigInteger classes (but then you'd have to perform calculations on the same instance, rather than returning a new one as is done now). Using the decimal calculation style is also fully unnecessary, computer use bytes and words of various sizes. This is doubly true because this just seems to be an implementation detail - the inner calculations are not exposed to the user.

Of course, LinkedList and other methods do already exist as well, and for specialized instructions it makes more much more sense to use arrays as they offer faster random access.

Java conventions

In general, this code looks to be written by somebody that normally programs in another PL. There are many hints of these:

1. Method name to_string() uses snake_case instead of camelCase. This is performed throughout the code.
2. Braces are on the next line instead of on the same line. This makes it harder to read for Java developers, either try and use the same style or reformat your code.
3. There are parentheses and casts to short that aren't necessary, showing that the developer doesn't fully trust Java expressions yet.
4. Access conditions are not very well used. The main class MyBigInt is not public, while it seems a generic class that doesn't contain any state. Node is not a static inner class but exposed to the outside, while it is clearly an implementation detail. It and the fields have package visibility which doesn't seem to be required.
5. ++(this.size) can just be expressed as this.size++ or even size++ although I personally like to indicate fields using this. Similar: --i is just confusing within the for loop, the loop will still start with the last index.
6. (int) (s.charAt(i) - '0') If you'd use a character in a constructor that requests an int parameter then it will be automatically converted / or widened. So the cast is not necessary.
7. to_string should be renamed to toString, which will automatically be used in e.g. a debugger to display the instance as it overrides Object.toString. This is why Java code conventions are a necessity; that way all Java code looks and behaves similarly, instead of having the hodge-podge of less structured languages.

Coding issues

an arbitrary number of digits

1. That's not the case if you define an int for size. OK, I guess that 2 billion or so digits is close enough, but arbitrary is larger. Just mention that it is limited in size by the positive integer value (i.e. Integer.MAX_VALUE`).

---

throw new IllegalStateException("Can't construct MyBigInt using an empty string!");

This should be an IllegalArgumentException. It should probably be more generic, throwing an exception if anything that doesn't represent a number is passed.

---

if (!(Character.isDigit(s.charAt(i))))

Although this is efficient, it would probably better if this was tested as guard statement at the front of the method - in advance of the main loop, and possibly by a method. See for instance this Q/A on SO.

private void trim_leading_zeroes() is called many times. This check could be performed during construction of numbers, or directly after or during calculations where necessary. Then the amount of state can be minimized and you'd always have correctly formatted numbers in your instances.

---

boolean is_greater_than_or_equal_to(MyBigInt n)

This isn't a great idea, there is a reason why there are methods that are called compare which return either a negative value - often -1, zero for equal or a positive value +1. Then you can use if x.compare(y) => 0 to perform your check.

Addition: in Java you'd implement the interface Comparable which provides the method compareTo so that all e.g. SortedList instances can rely on such functionality to be present.

---

if (ref_curr_node_1 != null)
...

This is very repetitive and it is not inherently bound to the methods that it is in, so this makes it logical to call a private implementation method.

Readability

It isn't clear which part of the number is the most and least significant digit. Devs will have to figure this out from the code, which is less than ideal. This could also be accomplished by renaming the class and fields of Node to e.g. DigitNode, and the fields to e.g. lowerDigitNode or higherDigitNode. The start of the list would then be e.g. leastSigDigNode or just least with a comment instead of ref_tail_node.

---

I have no idea why the number is generated from string least significant digit first, it makes much more sense to start with the head and move towards the tail. I also prefer to compare against index zero than comparing it to the index at the end of a string.

If there is a conscious design decision made for a specific implementation then please document it for the next developer. A simple description would not take much time for you - actually you might want to write it down when you're creating the class if just for yourself. It will save tons of headaches to the next developer in line, and that developer might be you in a couple of years.

---

MyBigInt add(MyBigInt n) one trick I learned is to name the parameter that (or other, but I prefer that. Then you can refer to them as this and that, very easy to distinguish instead of this and n. I don't see the point in renaming them to _1 and _2, that's even more confusing.