Different approach for algorithms and data structure implementation

  list of group members： Longfei Jiang、 Juntao Gao
  laboratory work number： 1
  variant description： Dynamic array (you can use built-in list inside node with fixed size)

Synopsis

  Develop libraries for specific data structures on classic development tasks. The selected data structure should be implemented in two ways:
    1、as a mutable object ;
    2、as an immutable object.

  For each version of the library (variable and immutable), the following functions should be implemented:
    1. add a new element;
    2. remove an element;
    3. size;
    4. conversion from and to python lists;
    5. find element by specific predicate;
    6. filter data structure by specific predicate;
    7. map structure by specific function;
    8. reduce – process structure elements to build a return value by specific functions;
    9. data structure should be a monoid and implement mempty and mconcat functions or methods;
    10. iterator;

  At last,you should use two approaches to test your code:
    1、unit tests (for all features);
    2、property-based tests (for features with specific properties, such as monoid properties).

Contribution summary for each group member

  Longfei Jiang: Complete the mutable object and immutable object data structures, and most of test functions.
  Juntao Gao: Partial data structure methods are implemented, as well as some test functions and final experimental reports.modify procedure

Explanation of taken design decisions and analysis

  The data structure that our group needs to implement is a dynamic array. The difference between a dynamic array and a fixed array is that the length of the dynamic array is variable, so we implement our own dynamic array by encapsulating the static array.
  Using static arrays as attributes of the Python class, you can use built-in lists within nodes of fixed size. Of course, what we have implemented is a dynamic array, which can be expanded by inserting data in the head or tail. Then complete some common methods of dynamic array required by the experiment, such as array length, map and iterator.

How to use developed software

一、for the mutable object
  1、size
  DA_mut([1, 2, 3]).size
  2、to_list
  DA_mut([1, 2, 3]).to_list()
  3、from_list
  

    test_data = [
            [],
            ['a'],
            ['a', 'b']
        ]
        for e in test_data:
            lst = DA_mut()
            lst.from_list(e)

  4、add_to_head
  lst = DA_mut()
  lst.add_to_head('a')
  5、add_to_tail
  lst = DA_mut()
  lst.add_to_tail('a')
  6、map
  lst = DA_mut()
  lst.from_list([1, 2, 3])
  lst.map(str)
  7、reduce
  lst = DA_mut()
  lst.from_list([1, 2, 3])
  lst.reduce(lambda st, e: st + e, 0)
  8、find
  lst = DA_mut([1,2,3])
  lst.find(1)
  9、filter
  lst = DA_mut([1,2,1])
  lst.filter(1)
  10、mempty
  lst = DA_mut([1, 2, 3])
  lst.mconcat()
  11、filter
  lst1 = DA_mut([1, 2, 3])
  lst2 = DA_mut([1, 2, 3])
  lst1.mconcat(lst2)
  lst1.to_list()
  12、remove
  lst = DA_mut([1, 2, 3])
  lst.remove(1)
  13、iter

        x = [1, 2, 3]
        lst = DA_mut()
        lst.from_list(x)
        tmp = []
        for e in lst:
            tmp.append(e)

二、for the immutable object
  1、size
  size(DA_imm([])
  2、to_list
  lst = [1, 2]
  a = DA_imm(lst)
  b = to_list(a)
  3、from_list
  

        test_data = [
            [],
            ['a'],
            ['a', 'b']
        ]
        for e in test_data:
            lst = from_list(e)

  4、add_to_head
  DA1 = add_to_head(DA_imm([]), 1)
  5、add_to_tail
  DA1 = add_to_tail(DA_imm([1, 2]), 1)
  6、map
  a = DA_imm([1,2,3])
  b = map(a,str)
  7、reduce
  lst = DA_mut()
  reduce(lst,(lambda st, e: st + e)
  8、find
  lst = DA_mut([1,2,3])
  find(a, 1)
  9、filter
  lst = DA_mut([1,2,1])
  b = filter(a,2)
  10、mconcat
  a = DA_imm([1,2])
  b = DA_imm([1,2])
  c = mconcat(a,b)
  11、iter

        x = [1, 2, 3,4]
        lst = from_list(x)
        tmp = []
        try:
            get_next = iterator(lst)
            while True:
                tmp.append(get_next())
        except StopIteration:
            pass

Conclusion

  For mutable objects and immutable objects, we find that once a mutable object is created, it can be changed but the address will not change, that is, the variable points to the original object. Immutable objects are the opposite. They cannot be changed after creation. If they are changed, the variable points to a new object.
  During the iterator testing process, we found that when an empty object is passed in, it will cause an error in the dynamic array length measurement method, resulting in an error in the iterator. So we modified the size () function and added the treatment of empty objects To solve this problem.