Проблема ежедневного кодирования Java #006

Ежедневная проблема с кодированием – это веб-сайт, который каждый день будет отправлять вам задачу по программированию на ваш почтовый ящик. Я хочу показать новичкам, как решить некоторые из этих проблем с помощью Java, так что это будет продолжающаяся серия моих решений. Не стесняйтесь выбирать их отдельно в комментариях!

Проблема

Связанный список XOR – это более эффективный с точки зрения памяти двусвязный список. Вместо того, чтобы каждый узел, удерживающий следующий и предыдущие поля, он содержит поле с именем оба , которое является XOR следующего узла и предыдущего узла. Реализуйте связанный список XOR; в нем есть add(element) , который добавляет элемент в конец, и get(index) , который возвращает узел по индексу.

Если вы используете язык, который не имеет указателей (например, Python), вы можете предположить, что у вас есть доступ к get_pointer получить указатель и dereference_pointer функции, которые преобразуют между узлами и адресами памяти.

Стратегия

Спойлеры! Не смотрите ниже, если не хотите увидеть мое решение!

Двусвязные списки

Итак, во-первых, мне нужно понять, что такое двусвязный список. Итак, я прочитал статью в Википедии и, как я понимаю, это так:

Каждый элемент односвязного списка (или просто связанный список ) содержит:

• некоторые данные
• указатель или ссылка на следующий элемент в списке

Каждый элемент двусвязного списка содержит:

• некоторые данные
• указатель или ссылка на следующий элемент в списке
• указатель или ссылка на предыдущий элемент в списке

Вы можете визуализировать различия между этими типами списков следующим образом:

Односвязные списки можно просматривать только в прямом направлении. Элемент списка понятия не имеет, какой элемент был перед ним (если таковой имелся), и не имеет возможности получить к нему доступ. Двусвязный список можно просматривать в любом направлении, как вперед, так и назад. Когда пользователь пытается выйти за пределы конца списка (или за пределы начала списка для списка с двойной связью), должна быть выдана какая-либо ошибка или должен быть возвращен null .

Далее… что такое список XOR? Подсказка как бы объясняет концепцию, но я не уверен, что понимаю ее. Я вернусь к этому немного позже.

Строгая интерпретация подсказок

Я нашел этот ответ SO , который довольно хорошо объясняет плюсы и минусы двусвязных списков. Это также дает хорошее объяснение того, почему мы могли бы захотеть его использовать. Если позволите, я перефразирую…

В “истинном” односвязном или двусвязном списке мы храним два объекта:

1. данные
2. указатель или ссылка на другой элемент списка

Указатель – это просто еще одна переменная, которая содержит адрес памяти. В качестве примера предположим, что у нас есть двусвязный список C-language int s, длина которых составляет 4 байта . Указатели в C на 64-разрядной машине будут иметь длину 8 байт , поэтому для каждого элемента нашего списка требуется 20 байт для int и двух указателей.

Давайте предположим, что первый элемент списка находится по адресу 0x9A7D …

Префикс 0x указывает на то, что это шестнадцатеричное число. На 64-разрядной машине (где 64-разрядный относится к размеру адресного пространства памяти) для представления любого адреса требуется 8 байт. Один байт (диапазон 0-255) может быть представлен двумя шестнадцатеричными цифрами. Таким образом, для 8 байт требуется 16 шестнадцатеричных цифр.

В нашем примере этот адрес ссылается на значение , сохраненное этим элементом списка. Поскольку это значение является int , оно займет четыре байта пространства (восемь шестнадцатеричных цифр). Следующие 8 байт (шестнадцать шестнадцатеричных цифр) будут указателем на “следующий” элемент в списке, а последние 8 байт будут указателем на “предыдущий” элемент в списке, поэтому:

D0 C0 FF EE [ "next" address      ] [ "previous" address  ]
^^^^^^^^^^^
4-byte integer value (hex "D0 C0 FF EE" = decimal "3 502 309 358")

Если первый элемент списка (этот) находится по адресу

0x9E7D6300BA679A7D

…затем следующий элемент будет смещен на 20 байт (при условии, что элементы списка хранятся в непрерывном блоке памяти, что может быть не так), в

0x9E7D6300BA679A91

0x7D + +

D0 C0 FF EE 9E 7D 63 00 BA 67 9A 91 [ "previous" address  ]
            ^^^^^^^^^^^^^^^^^^^^^^^
             "next" memory address

Аналогично, “предыдущий” адрес будет смещен на 20 байт в противоположном направлении для всех элементов списка, кроме этого первого. Поскольку у первого элемента нет “предыдущего” адреса, будет некоторый индикатор того, что там нет элемента (возможно, нулевой указатель на адрес памяти 0x0 ):

D0 C0 FF EE 9E 7D 63 00 BA 67 9A 91 00 00 00 00 00 00 00 00
                                    ^^^^^^^^^^^^^^^^^^^^^^^
                                   "previous" memory address

В C мы, очевидно, не будем работать напрямую с этими байтами. Вместо этого у нас будет что-то вроде :

struct DLL {

  int data; // value
  struct DLL *next;
  struct DLL *previous;

}

… но как, черт возьми, мы могли бы реализовать это на Java? Java заимствует много синтаксиса из C/C++, но в нем нет struct s. Итак, в Java вместо этого мы могли бы иметь :

class DLL {

  int value; 
  /* implement next */
  /* implement previous */

}

Java также не имеет указателей, но помните, что в приглашении указано:

Если вы используете язык, который не имеет указателей (например, Python), вы можете предположить, что у вас есть доступ к get_pointer получить указатель и разыменование_поинтер_ функции, которые преобразуют между узлами и адресами памяти.

Java, разработанный как “безопасный” язык, не позволяет вам возиться с адресами памяти . Так что get_pointer и методы dereference_pointer являются чисто воображаемыми. Судя по описанию приглашения, они должны иметь подписи типов, такие как:

DLL* get_pointer (DLL link)

DLL dereference_pointer (DLL* pointer)

…которые преобразуют объект DLL в указатель, содержащий его адрес в памяти, и наоборот. Проблема предполагает выполнение чего-то вроде:

public class DLL {

  public  int  data; // value
  private DLL  next;
  private DLL  previous;

  public  DLL* next()     { return get_pointer(next)     }
  public  DLL* previous() { return get_pointer(previous) }

}

Это уродливо. Это также недопустимый синтаксис Java. В реальной жизни это бесполезно. Я не думаю, что стоит продолжать это гипотетическое решение.

Переосмысление подсказки

Вместо того, чтобы следовать подсказке до буквы, давайте немного переосмыслим ее, чтобы мы действительно могли уловить дух связанных списков XOR в Java.

Мы могли бы попытаться использовать java.lang.instrument для определения размеров (в байтах) объектов в Java , но такой подход дает неинтуитивные результаты ( все String имеют одинаковый размер), которые не полезны для наших целей (зная фактический размер объекта в памяти).

Вместо этого давайте смоделируем адреса памяти. Java допускает шестнадцатеричные литералы и (по умолчанию) преобразует их в десятичные при печати:

jshell> 0x10
$3 ==> 16

jshell> 0x20
$4 ==> 32

jshell> 0x10 + 0x10
$5 ==> 32

Поскольку Java int имеет диапазон [-2e31, 2e31-1] ( [-2147483648, 2147483647] ), его максимальные шестнадцатеричные значения равны:

jshell> 0x0
$31 ==> 0

jshell> 0x7FFFFFFF
$32 ==> 2147483647

jshell> 0x80000000
$33 ==> -2147483648

jshell> 0xFFFFFFFF
$34 ==> -1

Таким образом, мы можем создать метод, который “выделяет” адрес памяти для нового объекта, учитывая размер объекта. Мы можем отслеживать, какие “ячейки памяти” используются, чтобы случайно не “перезаписать” старые данные. Затем мы, наконец, сможем реализовать связанный с XOR список (который будет объяснен во время его реализации) на Java.

Код

Для начала давайте создадим простой класс Memory в Java:

public class Memory {

  private static Random random = new Random();

  // return any address except "0x00000000", the "NULL" address
  public static String randomAddress() {
    int value = random.ints(1L, Integer.MIN_VALUE, Integer.MAX_VALUE).toArray()[0] + 1;
    return intToAddress(value);
  }

  public static int addressToInt(String address) {
    return (int)(Long.parseLong(address.substring(2), 16) + Integer.MIN_VALUE);
  }

  public static String intToAddress(int value) {
    long longValue = (long)value - (long)Integer.MIN_VALUE;
    return String.format("0x%8s", Long.toString(longValue, 16).toUpperCase()).replaceAll(" ", "0");
  }

}

Этот класс имеет три функции: int To Address() , который принимает любое значение int в качестве аргумента и преобразует его в шестнадцатеричный адрес Строка , адрес В Int() , который выполняет обратное, и случайный адрес() , который генерирует случайный адрес Строка . Репозиторий GitHub, в котором размещен этот код

jshell> Memory.randomAddress()
$195 ==> "0xB821DAE5"

jshell> Memory.addressToInt("0xB821DAE5")
$196 ==> 941742821

jshell> Memory.intToAddress(941742821)
$197 ==> "0xB821DAE5"

Максимальные значения для int Для Address() равны Integer. МИНИМАЛЬНОЕ ЗНАЧЕНИЕ и Целое число. MAX_VALUE МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ//:

jshell> Memory.intToAddress(Integer.MIN_VALUE)
$198 ==> "0x00000000"

jshell> Memory.intToAddress(Integer.MAX_VALUE)
$199 ==> "0xFFFFFFFF"

… которые возвращают максимальные значения для адреса В Int() :

jshell> Memory.addressToInt("0x00000000")
$200 ==> -2147483648

jshell> Integer.MIN_VALUE
$201 ==> -2147483648

jshell> Memory.addressToInt("0xFFFFFFFF")
$202 ==> 2147483647

jshell> Integer.MAX_VALUE
$203 ==> 2147483647

Обратите внимание, что моя реализация “максимальных” и “минимальных” шестнадцатеричных значений отличается от Java, которые переносятся в 0x7FFFFFFF / 0x80000000 . Я перестроил так, чтобы минимальное шестнадцатеричное значение соответствовало наименьшему адресу памяти, что, на мой взгляд, немного более интуитивно понятно.

Далее нам нужно “выделить память”, когда мы создаем новый объект (в данном случае наш объект с двойным списком). Когда мы делаем это, нам нужно указать необходимый объем памяти. Давайте создадим malloc -подобная функция для памяти :

  public static String malloc(long size) {

    // if object has zero size, return NULL address
    if (size < 1) return "0x00000000";

    // if object cannot fit in memory, throw error
    if (size > (long)Integer.MAX_VALUE - (long)Integer.MIN_VALUE )
      throw new IllegalArgumentException("insufficient memory");

    // if object can fit in memory, get largest possible address

    long first = Integer.MIN_VALUE;
    long last  = (long)Integer.MAX_VALUE - size;

    // if only one possible memory address, return that one
    if (first == last) return "0x00000001";

    // ...else, randomise over valid range
    int value = random.ints(1L, (int)first, (int)last).toArray()[0] + 1;

    // ...and return as address
    return intToAddress(value);

  }

Это, конечно, чрезвычайно простой и неэффективный способ выделения памяти. Есть лучшие решения , но они требуют немного больше работы. Давайте пока воспользуемся этим простым решением. Наконец, нам нужен способ “зарегистрировать” память, чтобы мы случайно не перезаписали объект другим.

  // keep track of which int-indexed blocks are occupied by data
  private static HashSet occupied = new HashSet<>(Arrays.asList(Integer.MIN_VALUE));

  // free memory within a certain range
  public static void free(String iAddress, String fAddress) {
    int iAdd = addressToInt(iAddress);
    int fAdd = addressToInt(fAddress);

    // remove all addresses in range
    occupied.removeAll(IntStream.range(iAdd, fAdd).boxed().collect(Collectors.toList()));

    // check that "NULL" is still "occupied"
    occupied.add(Integer.MIN_VALUE);
  }

  // free all memory
  public static void free() {
    free("0x00000001", "0xFFFFFFFF");
  }

  // list of objects in memory
  public static HashMap refTable = new HashMap<>();
  static { refTable.put("0x00000000", null); }

  // dereference object
  public static Object dereference(String address) {
    return refTable.get(address);
  }

Вышесказанное, конечно, на самом деле не работает, так как мы не проверяем в malloc , зарегистрирована память или нет. Чтобы иметь полностью работающее, надежное решение, нам понадобился бы гораздо более сложный механизм распределения памяти. Но в любом случае, этого, вероятно, достаточно, чтобы немного поиграть:

jshell> Memory.occupied
$83 ==> [-2147483648]

jshell> Memory.malloc(1)
$84 ==> "0xB8B7087E"

jshell> Memory.occupied
$85 ==> [-2147483648, 951519358]

jshell> Memory.intToAddress(951519358)
$86 ==> "0xB8B7087E"

jshell> Memory.malloc(2)
$87 ==> "0x802AD3C8"

jshell> Memory.occupied
$88 ==> [-2147483648, 2806728, 2806729, 951519358]

Наконец мы можем начать говорить о списках, связанных с XOR.

Списки, связанные с XOR

Вспомните определение двусвязного списка, приведенное ранее:

Каждый элемент двусвязного списка содержит:

• некоторые данные
• указатель или ссылка на следующий элемент в списке
• указатель или ссылка на предыдущий элемент в списке

Итак, нам нужен класс Node s для элементов списка и Двусвязный список класс. Простой Node класс может выглядеть следующим образом:

  class Node {

    // number of "bytes" to allocate for a DLL
    static final int size = 20;

    U      data; // data held by this DLL element
    String next; // address of next DLL element
    String prev; // address of previous DLL element
    String addr; // address of this DLL element

    // constructor with no "next" or "prev" elements
    public Node (U data) {

      this.data = data;
      this.next = "0x00000000"; // null
      this.prev = "0x00000000"; // null

      // allocate memory for this DLL element
      this.addr = Memory.malloc(size);

    }
  }

Мы можем добавить методы для получения и установки адресов следующий и предыдущий (предыдущие) узлы в списке:

    // method to get a "pointer" to this object ("get_pointer")
    String ptr() { return this.addr; }

    // getters for next and prev
    String next() { return this.next; }
    String prev() { return this.prev; }

    // setters for next and prev
    void next(String addr) { this.next = addr; }
    void prev(String addr) { this.prev = addr; }

Наконец, нам нужен способ “выделения памяти” для этих объектов, присвоения им адреса памяти и “разыменования” этого адреса. Для нашего Двусвязного списка и Node classes чтобы получить доступ к нашему Memory классу, нам нужно упаковать их в *.jar . Я создам проект Maven со всем этим кодом. Затем мы можем развернуть объект Двусвязный список …

public class DoublyLinkedList {

  // List of Nodes
  private List> Nodes;

  // get number of Nodes in this List
  public int size() { return this.Nodes.size(); }

  // constructor
  public DoublyLinkedList() {
    this.Nodes = new ArrayList<>();
  }

  // add a Node to the end of the List
  public DoublyLinkedList add(T t) {
    Node newNode = new Node<>(t);

    // if this List already has Nodes
    if (this.size() > 0) {

      // get Node which previously was last Node
      Node oldLastNode = this.Nodes.get(this.size()-1);

      // edit last Node in List to point to _new_ last Node
      oldLastNode.next = newNode.ptr();

      // edit new last Node to point to _old_ last Node
      newNode.prev(oldLastNode.ptr());
    }

    // add new last Node to end of List
    this.Nodes.add(newNode);

    // so add() can be chained
    return this;
  }

  /* Node inner class */

}

Теперь мы можем использовать Node.ptr() для получения “адреса” элемента Node и адресов ” dereference() ” для получения объектов, на которые они ссылаются (примечание что я также @Переопределить методы по умолчанию toString() для Узла и Двусвязный список ):

$ jshell -cp target/006-1.0-SNAPSHOT.jar
|  Welcome to JShell -- Version 11.0.2
|  For an introduction type: /help intro

jshell> import DCP.*

jshell> DoublyLinkedList dll = new DoublyLinkedList<>();
dll ==> 

jshell> dll.add(1)
$3 ==> 
0x00000000 <- 0xA0EAA2D0 -> 0x00000000
      null <-          1 ->       null

jshell> dll.add(2)
$4 ==> 
0x00000000 <- 0xA0EAA2D0 -> 0x29728E8A
      null <-          1 ->          2

0xA0EAA2D0 <- 0x29728E8A -> 0x00000000
         1 <-          2 ->       null

jshell> dll.add(3)
$5 ==> 
0x00000000 <- 0xA0EAA2D0 -> 0x29728E8A
      null <-          1 ->          2

0xA0EAA2D0 <- 0x29728E8A -> 0x5DBD6A3C
         1 <-          2 ->          3

0x29728E8A <- 0x5DBD6A3C -> 0x00000000
         2 <-          3 ->       null

Переопределяя toString() , у меня есть каждый Узел укажите его адрес, а также адреса следующего и предотвращать Node s в первой строке и их значения во второй строке:

0xA0EAA2D0 <- 0x29728E8A -> 0x5DBD6A3C
         1 <-          2 ->          3

Со списком, связанным с XOR , вместо удержания обоих тот предыдущий и следующие адреса, мы сохраняем XOR этих адресов:

jshell> Memory.addressToInt("0xA0EAA2D0")
$7 ==> 552248016

jshell> Memory.addressToInt("0x5DBD6A3C")
$8 ==> -574789060

jshell> $7 ^ $8
$9 ==> -44578580

jshell> Memory.intToAddress($9)
$10 ==> "0x7D57C8EC"

Списки, связанные с XOR, не могут разрешать произвольный доступ. Мы должны начать либо с начала, либо с конца списка и продвигаться вниз по списку. Если мы начнем с первого Узла из нашего приведенного выше списка, например:

0x00000000 <- 0xA0EAA2D0 -> 0x29728E8A
      null <-          1 ->          2

jshell> int both = (Memory.addressToInt("0x00000000") ^ Memory.addressToInt("0x29728E8A"))
both ==> 695373450

jshell> Memory.intToAddress(both)
$12 ==> "0xA9728E8A"

“Чтобы начать просмотр списка в любом направлении с некоторой точки, требуется адрес двух последовательных элементов. Если адреса двух последовательных элементов поменять местами, обход списка будет происходить в противоположном направлении” — Вики

В приведенной выше цитате из Википедии отмечается, что нам нужен адрес предыдущего элемента, а также оба для обхода списка:

jshell> Memory.intToAddress(both ^ Memory.addressToInt("0x00000000"))
$18 ==> "0x29728E8A"

Для второго элемента в нашем списке выше:

jshell> int both = (Memory.addressToInt("0xA0EAA2D0") ^ Memory.addressToInt("0x5DBD6A3C"))
both ==> -44578580

jshell> Memory.intToAddress(both)
$20 ==> "0x7D57C8EC"

jshell> Memory.intToAddress(both ^ Memory.addressToInt("0xA0EAA2D0"))
$21 ==> "0x5DBD6A3C"

Мы видим, что нам нужен предыдущий адрес и XOR оба , чтобы получить следующий адрес, или следующий адрес и XOR оба , чтобы получить предыдущий адрес. Нам не нужно хранить два адреса в каждом Узле , но нам нужно отслеживать адрес этого предыдущего Узла где-то . В целом, это довольно неуклюжая структура данных с небольшой пользой . Возможно, это было более полезно в первые дни вычислительной техники, когда память была на высоте, но сейчас, вероятно, лучше избегать этого. (Не говоря уже о том, что на самом деле это невозможно реализовать на Java.)

Обсуждение

Это было интересное упражнение, но в основном по причинам, которые не имели ничего общего с фактическим приглашением. Изучение шестнадцатеричных литералов в Java, преобразование между ними и целыми числами, реализация поддельного хранилища объемом 4 ГБ с адресом NULL , подделка указателей и разыменование… все это было действительно интересно и познавательно. Списки, связанные с XOR? Не так сильно.

В будущем я мог бы попытаться повторно реализовать свое поддельное пространство памяти с помощью лучшего malloc . Я думаю, что это было бы действительно познавательным испытанием. Как ты думаешь?

Весь код для решения моих ежедневных проблем с кодированием доступен по адресу github.com/awwsmm/daily .

Предложения? Дайте мне знать в комментариях.

Оригинал: “https://dev.to/awwsmm/java-daily-coding-problem-006-2l98”